Share my solution in Segment-Tree(O(NlogK) Time 100ms)


  • 3
    I
    class Solution {
        public:
            /**
             * @param nums: A list of integers.
             * @return: The maximum number inside the window at each moving.
             */
            class SegmentTreeNode {
            public:
                int start, end, max;
                SegmentTreeNode *left, *right;
                SegmentTreeNode(int start, int end, int max) {
                    this->start = start;
                    this->end = end;
                    this->max = max;
                    this->left = this->right = NULL;
                }
            };
            SegmentTreeNode * build(int start, int end, vector<int> &A) {
                // write your code here
                if (start > end) return NULL;
                if (start == end) {
                    SegmentTreeNode *root = new SegmentTreeNode(start, end, A[start]);
                    return root;
                }
                int mid = start + (end - start) / 2;
                SegmentTreeNode *root = new SegmentTreeNode(start, end, A[mid]);
                root->left = build(start, mid, A);
                root->right = build(mid + 1, end, A);
                root->max = max(root->left->max, root->right->max);
                return root;
            }
            void modify(int pos, int val, SegmentTreeNode *root) {
                if (root->start == root->end) {
                    root->max = val;
                    return;
                }
                int mid = root->start + (root->end - root->start) / 2;
                if (pos <= mid) modify(pos, val, root->left);
                else modify(pos, val, root->right);
                root->max = max(root->left->max, root->right->max);
            }
            vector<int> maxSlidingWindow(vector<int> &nums, int k) {
                // write your code here
                vector<int> res;
                if (k <= 0 || nums.empty()) return res;
                int len = nums.size();
                SegmentTreeNode *root = build(0, min(k - 1, len - 1), nums);
                res.push_back(root->max);
                for (int i = k; i < nums.size(); i ++) {
                    modify(i % k, nums[i], root);
                    res.push_back(root->max);
                }
                return res;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.