leetcode：795.区间子数组个数【单调栈当前元素为最大覆盖的区间+java练习】

• 无脑单调栈左右找更大
• 注意一边不取等&＃xff0c;一边取等&＃xff0c;避免重复
• 找到包含当前元素为最大值的区间个数&＃xff0c;左 * 右即可

class Solution:def numSubarrayBoundedMax(self, nums: List[int], left_: int, right_: int) -> int:# 单调栈n &＃61; len(nums)# 左边比自己大的最近的位置left, st &＃61; [-1] * n, []for i, v in enumerate(nums):while st and nums[st[-1]] < v: st.pop()if st: left[i] &＃61; st[-1]st.append(i)# 右边比自己大于等于的最近的位置right, st &＃61; [n] * n, []for i in range(n - 1, -1, -1):while st and nums[st[-1]] <&＃61; nums[i]: st.pop()if st: right[i] &＃61; st[-1]st.append(i)# 当前元素作为最大值的区域#print(left)#print(right)ans &＃61; 0for i in range(n):l, r &＃61; i - left[i], right[i] - iif left_ <&＃61; nums[i] <&＃61; right_:#print(nums[i], l, r)ans &＃43;&＃61; l * rreturn ans

java

class Solution {public int numSubarrayBoundedMax(int[] nums, int left, int right) {// java单调栈int n &＃61; nums.length;int[] L &＃61; new int[n], R &＃61; new int[n];Arrays.fill(L, -1);Arrays.fill(R, n);Deque<Integer> st &＃61; new ArrayDeque<>();// 左边比自己大的最近的位置for (int i &＃61; 0; i < n; &＃43;&＃43;i) {while (!st.isEmpty() && nums[st.peek()] < nums[i]) st.pop();if (!st.isEmpty()) L[i] &＃61; st.peek();st.push(i);}// 右边比自己大于等于的最近的位置st.clear();for (int i &＃61; n - 1; i >&＃61; 0; --i) {while (!st.isEmpty() && nums[st.peek()] <&＃61; nums[i]) st.pop();if (!st.isEmpty()) R[i] &＃61; st.peek();st.push(i);}// 当前元素作为最大值的区域int ans &＃61; 0;for (int i &＃61; 0; i < n; &＃43;&＃43;i) {if (left <&＃61; nums[i] && nums[i] <&＃61; right) {ans &＃43;&＃61; (i - L[i]) * (R[i] - i);}}return ans;}
}


• int[] l &＃61; new int[n];
• Deque st &＃61; new ArrayDeque<>();
• st.peak()
• st.pop()
• st.push(i)

• 单调栈无脑
• 继续熟悉java