239. Sliding Window maximum Leetcode Solution

class SegmentTree{
    int seg[4*100000];
    public:
    void build(int ind, int low, int high, vector< int>&nums){
        if(low==high){
            seg[ind] = nums[low];
            return;
        }
        int mid = (low+high)/2;
        build(2*ind+1,low,mid,nums);
        build(2*ind+2,mid+1,high,nums);
        seg[ind] = max(seg[2*ind+1],seg[2*ind+2]);
    }
    int rangeQuery(int low, int high, int l, int r, int ind){
        if(low>=l && high< =r){
            return seg[ind];
        }
        if(r< low || l>high){
            return INT_MIN;
        }
        int mid = low + (high-low)/2;
        return max(rangeQuery(low,mid,l,r,2*ind+1),rangeQuery(mid+1,high,l,r,2*ind+2));
    }
};

class Solution {
public:
    vector< int> maxSlidingWindow(vector< int>& nums, int k) {
        int n = nums.size();
        SegmentTree st;
        vector< int>v;
        st.build(0,0,n-1,nums);
        for(int i=0;i< =n-k;i++){
            v.push_back(st.rangeQuery(0,n-1,i,i+k-1,0));
        }
        return v;
    }
};

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque< Integer> q = new ArrayDeque<>();  // stores *indices*
        List< Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast();
            }
            q.addLast(i);
            // remove first element if it's outside the window
            if (q.getFirst() == i - k) {
                q.removeFirst();
            }
            // if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
            if (i >= k - 1) {
                res.add(nums[q.peek()]);
            }
        }
        return res.stream().mapToInt(i->i).toArray();            
    }
}

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        from collections import deque
        q = deque() # stores *indices*
        res = []
        for i, cur in enumerate(nums):
            while q and nums[q[-1]] <= cur:
                q.pop()
            q.append(i)
            # remove first element if it's outside the window
            if q[0] == i - k:
                q.popleft()
            # if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
            if i >= k - 1:
                res.append(nums[q[0]])
        return res