单调栈

907. 子数组的最小值之和 - 力扣（LeetCode）

贡献法 求每个数能为答案贡献多少度 那就要看 他在几个子数组里是最小值 那就分别去找 这个数两边 是不是有比他更小的数

一个数能提供的度数 就是a * （i - l）*（r - i） 其中l， r 为他左右比他更小的数的下标 没有就是-1 或 n

要找这样的数 每个数的前后比他更小的 就用单调栈

从左往右 放入数 一旦遇到比栈顶小的 就pop 直到比栈顶大或栈为空 放入元素 更新下标

此时 把栈顶踢出的（i）是栈顶的右边界 而最终停止pop后 如果栈顶有元素（说明是比i小的）就是i的左边界

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        mod = 10 ** 9 + 7
        n = len(arr)
        left, right = [-1] * n, [n] * n
        st = []
        i = 0
        for i, x in enumerate(arr):
            while st and arr[st[-1]] <= x:
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(x)
        res = sum(a * (i - l) * (r - i) for i, (l, r) in enumerate(zip(left, right)))
        return res

2454. 下一个更大元素 IV - 力扣（LeetCode）

要找到下下个更大的元素 其实就是用单调栈 一个单调栈用于找下一个更大的元素 两个单调栈就可以找下下个更大的元素

st1存放 (暂时没找到比他大的)元素 st2存放(已经有一个比他大)的元素

每次先判断当前元素x 是否大于st2中的元素 如果是 就直接更新ans

然后判断有多少个st1中的数可以被更新到st2

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        st1 = []
        st2 = []
        ans = [-1] * n
        for i, x in enumerate(nums):
            while st2 and nums[st2[-1]] < x:
                ans[st2.pop()] = x
            j = len(st1) - 1
            while j >= 0 and nums[st1[j]] < x:
                j -= 1
            st2 += st1[j + 1:]
            del st1[j + 1:]
            st1.append(i)
        return ans

1673. 找出最具竞争力的子序列 - 力扣（LeetCode）

主要是没看出来是用单调栈的题目

一般来说需要从小到大（比如每日温度那个题）就是用单调栈

这个题目就满足 为了取最小的数 需要小数放前面 大数放后面 而且要按照数组中出现的顺序 所以可以考虑用单调栈

特别的是 这个题还有数量要求 必须是k个数字

那就设置last = n - k 表示pop的次数 在单调栈循环内 如果pop超过了last次 后面就不再pop了 否则数量不够k个 在单调栈循环结束后 如果last大于0 表示超过了k个数 需要再pop掉last次 由于小的数字放越前面越好 所以pop肯定是越早越好 所以就是遇到可以pop的就pop 后面的次数不够了就直接push进来

然后注意这题单调栈里面放的是数 不是下标

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) 
    {
        int n = nums.size();
        int last = n - k;
        vector<int>st;
        for (int i = 0; i < n; i++)
        {
            while (!st.empty() && last > 0 && st.back() > nums[i])
            {
                st.pop();
                last--;
            }
        }
        while(last--)
            st.pop();
        return st;
    }
};

滑动窗口

2302. 统计得分小于 K 的子数组数目 - 力扣（LeetCode）

这题首先是个数学问题 当出现连续的子数组的时候 每次答案增加的数量是 r - l + 1 知道这个之后就好想到滑动窗口

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) 
    {
        int n = nums.size();
        long long ans = 0L;
        int l = 0;
        long long sum = 0L;
        for (int r = 0; r < n; r++)
        {
            sum += nums[r];
            while (sum * (r - l + 1) >= k) // zhu'yi'shi
            {
                sum -= nums[l++];
            }
            ans += r - l + 1;
        }
        return ans;

    }
};