Monotonic Queue, two pointer and Greedy Algorithm

LeetCode 1793. Maximum Score of a Good Subarray

Problem

LeetCode 1793. Maximum Score of a Good Subarray

Code

Monotonic queue

For each element, this element will be the mininum value in range l to r.

We use L to record the l for element i. R to record the r for the element i. Where l and r are indice.

For element i, the left most is l and rightmost is r. mums[l:r+1] has the minimum element nums[i]. L[i] = l, R[i] = r

class Solution {
public:
    vector<int> helper(vector<int> nums, bool reverse_array) {
        if (reverse_array) {
            reverse(nums.begin(), nums.end());
            return helper(nums, false);
        }
        vector<int> queue, ret;
        const int n = nums.size();
        queue.reserve(n);
        ret.resize(n);
        queue.push_back(0);
        for (int i = 1; i < n; ++i) {
            while (!queue.empty() && nums[queue.back()] >= nums[i]) {
                queue.pop_back();
            }
            ret[i] =queue.empty()? 0:queue.back() + 1;
            queue.push_back(i); 
        }
        return ret;
    }
    int maximumScore(vector<int>& nums, int k) {
        int ret = 0;
        const int n = nums.size();
        auto L = helper(nums, false);
        auto R = helper(nums, true); 
        reverse(R.begin(), R.end());
        for (int i = 0; i < n; ++i){
            auto l = L[i], r = n - 1 - R[i];
            if (k>= l && k <= r) {
                ret = max(ret, nums[i]*(r-l+1));
            }
        }
        return ret;
    }
};

Two pointer and greedy

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
       int i = k, j = k;
        const int n = nums.size();
       int ret = nums[k];
       int curr_min = nums[k];
        while (true) {
            if (i == 0 && j== n - 1)break;
            if (i == 0) {
                j++;
            }
            else if (j == n-1) {
                i--;
            }
            else if(nums[i-1] >= nums[j+1]){
                i--;
            } else {
                j++;
            }
            curr_min = min(curr_min, min(nums[i], nums[j]));
            ret = max(ret, curr_min*(j-i+1));
        }
        return ret;
    }
};