Problem: 3676. 碗子数组的数目

思路

这道题是739.每日温度的变形。在每日温度中，我们维护了一个单调递减栈。当前元素大于栈顶元素时，不断弹出栈顶元素，直到当前元素不再大于栈顶元素。弹出的过程中，记录答案。

回归这道题目，要求解满足 min(nums[l],nums[r])>max(nums[l+1],…,nums[r−1])min(nums[l], nums[r]) > max(nums[l + 1], …, nums[r - 1])min(nums[l],nums[r])>max(nums[l+1],…,nums[r−1]) 条件的子数组数量。lll 和 r r r 是左右两个边界。因为我们不知道左右边界哪个大，哪个小，因此需要分情况讨论，这样就能避免比较左右边界大小的问题：

  1. 当nums[l]<nums[r]nums[l]<nums[r]nums[l]<nums[r]时，min(nums[l],nums[r])=nums[l]min(nums[l], nums[r])=nums[l]min(nums[l],nums[r])=nums[l]，且nums[l+1],…,nums[r−1]nums[l+1],…,nums[r-1]nums[l+1],…,nums[r−1]范围内的数都小于nums[l]nums[l]nums[l],我们需要找到lll右侧最近的大于nums[l]nums[l]nums[l]的下标rrr。此时，左右边界的最小值大于中间元素的最大值，满足题意。换句话说，这不就是找下一个更大的元素的问题？
  2. 当nums[l]>nums[r]nums[l]>nums[r]nums[l]>nums[r]时，需要找到rrr左侧最近的大于nums[r]nums[r]nums[r]的下标lll。也就是找下一个更大元素的问题。

复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    // 单调栈的应用
    public long bowlSubarrays(int[] nums) {
        int n = nums.length;
        Deque<Integer> st = new ArrayDeque<>();
        long ans = 0;
        // 从左到右遍历
        for (int i = 0; i < n; i ++) {
            int x = nums[i];
            while (!st.isEmpty() && x >= nums[st.peek()]) {
                int j = st.poll();
                if (i - j + 1 >= 3) {
                    ans ++;
                }
            }
            st.push(i);
        }
        st.clear();
        // 从右到左遍历
        for (int i = n - 1;i >= 0; i --) {
            int x = nums[i];
            while(!st.isEmpty() && x > nums[st.peek()]) {
                int j = st.poll();
                if (j - i + 1 >= 3) {
                    ans ++;
                }
            }
            st.push(i);
        }
        return ans;
    }
}