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

• ``````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) {
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) {
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;
}
};``````

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