Liudamie用户2678
单调栈详解与leetcode相关题目
输入“/”快速插入内容
单调栈详解与leetcode相关题目
单调栈详解与leetcode相关题目
什么是单调栈？
简单的来说，就是存放有序数据的栈，单调栈也分为递增栈和递减栈。
单调递增栈：从栈底到栈顶数据从大到小。
单调递减栈：从栈底到栈顶数据从小到大。
模拟单调栈的实现
现在有一组数10、3、7、4、12.从左到右依次入栈，如果栈为空或入栈元素小于栈顶元素值，则入栈；否则，如果入栈会破坏栈道单调性，则需要把比入栈元素小的全部出栈。单调递减的栈反之。
•
10入栈时，栈为空，直接入栈，栈内元素为10。
•
3入栈时，栈顶元素10比3大，刚入栈，栈内元素为10，3。
•
7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7.
•
4入栈时，栈顶元素7比4大，则入栈时，栈内元素为10，7，4。
•
12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。
单调栈道代码
代码块
Deque<Integer> stack = new LinkedList<>();
for(int i=0;i<nums.length;i++){
while(!stack.isEmpty()&&stack.peek()<nums[i]){
stack.pop();
}
stack.push(nums[i]);
}
//或者逆序遍历
for(int i=nuns.length-1;i>=0;i--){
while(!stack.isEmpty()&&stack.peek()<nums[i]){
stack.pop();
}
stack.push(nums[i]);
}
代码块
int stack[numsSize];
int top = -1;
for(int i=0;i<numsSize;i++){
while(top!=-1&&stack[top]<nums[i]){
top--;
}
stack[++top]=nums[i];
}
Leetcode 496.下一个更大元素
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
代码块
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
int *ans = (int *)malloc(sizeof(int)*nums1Size);
memset(ans,-1,sizeof(int)*nums1Size);
int hash[10001];
memset(hash,-1,sizeof(int)*10001);
for(int i=0;i<nums1Size;i++){
hash[nums1[i]]=i;
}
int stack[nums2Size];
int top=-1;
*returnSize = nums1Size;
for(int i=0;i<nums2Size;i++){
while(top!=-1&&stack[top]<nums2[i]){
if(hash[stack[top]]!=-1){
ans[hash[stack[top]]]=nums2[i];
}
top--;
}
stack[++top]=nums2[i];
}
return ans;
}