单调队列与栈

一.题

1.

思路： 构建小压大的单调递减栈，对于每个栈的元素都进行处理并加到结果上

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int stk[10000000],top = 0;
        long long ans = 0;
        
        for(int i =0;i<arr.size();i++){
            while(top&&arr[i]<arr[stk[top-1]]){
                int cur = stk[--top];
                int l = top==0?-1:stk[top-1];
                ans = (ans+(long long)(cur-l)*(i-cur)*arr[cur])%(1000000007);
            }
            stk[top++] = i;
        }
        while(top){
            int cur = stk[--top];
            int l = top==0?-1:stk[top-1];
            ans = (ans+(long long)(cur-l)*(arr.size()-cur)*arr[cur])%(1000000007);
        }
        return ans;
    }
};

 2.

思路： 以每排都为一次底，然后压缩和第一题类似

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int maximalRectangle(vector<string>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;

        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> height(cols, 0); 
        int ans = 0; 

        for (int i = 0; i < rows; i++) {
       
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') height[j] += 1;  
                else height[j] = 0; 
            }

            int stk[cols + 2], top = 0;
            stk[top++] = -1; 

            for (int j = 0; j <= cols; j++) {
                while (top > 1 && (j == cols || height[stk[top - 1]] >= height[j])) {
                    int curHeight = height[stk[--top]]; 
                    int width = j - stk[top - 1] - 1; 
                    int area = curHeight * width; 
                    ans = max(ans, area); 
                }
                stk[top++] = j; 
            }
        }

        return ans;
    }
};

3.

思路：用单调栈收集每个可能是低点的位置，使得栈严格小压大，单调递增，然后方向遍历全部的元素与栈中元素比较来找距离最远的坡

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        
        int stk[50050],top = 0;
        int ans = 0;
        stk[top++] = 0;

        for(int i =0;i<nums.size();i++){
           if(nums[i]<nums[stk[top-1]])stk[top++] = i;
        }

        for(int i = nums.size()-1;i>=0;i--){
            while(top&&nums[i]>=nums[stk[top-1]]){
                int cur = stk[--top];
                int temp_l = i - cur;
                ans = max(ans,temp_l);
            }
        }
        return ans;
    }
};

4.

思路：还是利用单调栈的特性，大压小，开头从栈底部开始，同时用一个数组标记是不是在栈中

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int counts[26] = {0}; 
        bool inStack[26] = {false}; 
        char stk[10005];
        int top = 0; 

        for (char ch : s) 
            counts[ch - 'a']++;

        for (char ch : s) {
            if (inStack[ch - 'a']) {
                counts[ch - 'a']--;
                continue;
            }
            while (top > 0 && stk[top - 1] > ch && counts[stk[top - 1] - 'a'] > 0) {
                inStack[stk[top - 1] - 'a'] = false; 
                top--; 
            }

            stk[top++] = ch;
            inStack[ch - 'a'] = true; 
            counts[ch - 'a']--; 
        }

        string result;
        for (int i = 0; i < top; i++) result += stk[i];
        return result;
    }
};

 5.

思路：因为，鱼是吃右边的更小的鱼，所以方向遍历后往前，因为小不能吃大，为小压大，在用个cnt数组统计每条鱼进行的场数，用max来求最大值

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
   int n,ans = -1;
   cin>>n;

   vector<int> fish(n);
   for(int i = 0; i < n; i++)cin>>fish[i];

   vector<int> cnt(n,0);
   stack<int> stk;

   for(int i = n-1; i >= 0; i--){
       while(!stk.empty() && fish[i]>fish[stk.top()]){
           int cur = stk.top();stk.pop();
           cnt[i] = max(cnt[i]+1,cnt[cur]);  
        }
        stk.push(i);
        ans = max(ans,cnt[i]);
   }
   
   cout<<ans;
   return 0;
}

 6.算法竞赛进阶指南

思路：模拟过程即可

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include<queue>

using namespace std;

int main() {
    int cnt[14];
    int time[14];
    vector<vector<char>>tt(14, vector<char>(5, 0));

    for (int i = 1; i <= 13; i++){
        cnt[i] = 4; time[i] = 0;
        for (int j = 1; j <= 4; j++)
            cin >> tt[i][j];
    }
    cnt[13] = 1;
        
    while (cnt[13] <= 4) {
        char temp = tt[13][cnt[13]++];
        if (temp == 'K') continue;

        while (temp != 'K') {
            int num = 0;
            if (temp == 'A')num = 1;
            else if (temp == '0')num = 10;
            else if (temp == 'J')num = 11;
            else if (temp == 'Q')num = 12;
            else num = temp - '0';
   
            time[num]++;
            if (cnt[num] == 0)break;
            temp = tt[num][cnt[num]--];
        }
    }

    int ans = 0;
    for (int i = 1; i <= 12; i++) {
        if (time[i] == 4)ans++;
    }
    cout << ans;
    return 0;
}