今日学习记录
1. 碗子数组数目leetcode.3676
关键词：单调栈
问题分析：
- 问题其实很简单,找到所以像碗一样分布的数组就行,碗中间小两边大,求满足中间值小于两端点最小值的数组数
核心思路
- 开始被平衡碗限制了想像,但是要严格的证明,两端点一定不能装比左大的数,而且中间数也不能大于左端点,所以要找到右边第一个大于左端点的数,枚举左,查找右
- 还要讨论右端端点的情况,直接类似于枚举左,实现时不能使用双循环,会超时
- 利用单调栈的特性来维护左端点,在单调栈中,保持单调关系,一个元素比左边小,比较右边,右边比这个元素大,就找到符合条件的,踢出栈顶,若右边元素还比左元素大,那么说明中间元素都比左边小,且小于右边,则又得到符合条件的数
**最终代码：
long long bowlSubarrays(vector<int>& nums) {
long long ans = 0;
int n = nums.size();
stack<int> st;
for(int i = 0;i<n;i++){
int x = nums[i];
while(!st.empty()&&nums[st.top()]<x){
if(i-st.top()>1) ans++;
st.pop();
}
if(!st.empty()&&i-st.top()>1) ans++;
st.push(i);
}
return ans;
}学到的点：
- 单调栈应用