Lab Solutions

// LeetCode 20. Valid Parentheses [Hint: Use Stack]
bool isValid(string x) { // Complexity: O(n)
    stack<char> s;
    for(char c: x) {
        if(c == '(' or c == '{' or c == '[')
            s.push(c);
        else if(s.empty()) return false;
        else {
            char last = s.top();
            s.pop();
            if((last=='(' and c==')')
               or (last=='{' and c=='}')
               or (last=='[' and c==']'))
                ;
            else return false;
        }
    }
    return s.empty();
}


// Leetcode 1046. Last Stone Weight [Hint: Use Priority Queue]
int lastStoneWeight(vector<int>& stones) { // Complexity: O(n log n)
    priority_queue<int> pq(stones.begin(), stones.end());

    while(pq.size() > 1) {
        int y = pq.top(); pq.pop();
        int x = pq.top(); pq.pop();
        if(y > x) pq.push(y - x);
    }

    if(!pq.empty()) return pq.top();
    return 0;
}


// LeetCode 239. Sliding Window Maximum [Hint: Use Deque]
vector<int> maxSlidingWindow(vector<int>& nums, int k) { // Complexity: O(n)
    deque<int> dq;
    int n = nums.size();
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        if(!dq.empty() and dq.front()<=(i-k))
            dq.pop_front();

        while(!dq.empty() and nums[dq.back()] < nums[i])
            dq.pop_back();

        dq.push_back(i);
        if(i >= k - 1) ans.push_back(nums[dq.front()]);
    }

    return ans;
}