算法训练营Day59(单调栈）
下一个更大元素II
503. 下一个更大元素 II - 力扣（LeetCode）
最直接的方法，我自己写的。。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int len = nums.length*2;
int [] nums2 = new int[len];
for(int i = 0;i<len;i++){
if(i<len/2){
nums2[i]=nums[i];
}else{
nums2[i]=nums[i-len/2];
}
}
int[] res = new int[len/2];
Arrays.fill(res,-1);
Deque<Integer> statk = new LinkedList<>();
for(int i = 0;i<len;i++){
while(!statk.isEmpty()&&nums2[i]>nums2[statk.peek()]){
int pre = statk.pop();
if(pre<len/2){
res[pre] = nums2[i];
}
}
statk.push(i);
}
return res;
}
}优化
class Solution {
public int[] nextGreaterElements(int[] nums) {
//边界判断
if(nums == null || nums.length <= 1) {
return new int[]{-1};
}
int size = nums.length;
int [] res = new int[size];
Arrays.fill(res,-1);
Deque<Integer> stack = new LinkedList<>();
for(int i = 0;i<2*size;i++){
while(!stack.isEmpty()&&nums[i%size]>nums[stack.peek()]){
int pre = stack.pop();
res[pre] = nums[i%size];
}
stack.push(i%size);
}
return res;
}
}接雨水
接雨水这道题目是 面试中特别高频的一道题，也是单调栈 应用的题目，大家好好做做。
建议是掌握 双指针 和单调栈，因为在面试中 写出单调栈可能 有点难度，但双指针思路更直接一些。
在时间紧张的情况有，能写出双指针法也是不错的，然后可以和面试官在慢慢讨论如何优化。
单调栈也不是很难，理解好水平积累，巧用单调栈还是很容易的
class Solution {
public int trap(int[] height) {
if(height.length<=2){
return 0;
}
int res = 0;
Deque<Integer> stack = new LinkedList<>();
for(int i = 0;i<height.length;i++){
while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
int right = height[i];
int midIndex = stack.pop();
int mid = height[midIndex];
if(!stack.isEmpty()){
int leftIndex = stack.peek();
int left = height[leftIndex];
int h = Math.min(right,left) - mid;
int w = i-leftIndex-1;
res+=w*h;
}
}
stack.push(i);
}
return res;
}
}
原文地址：https://blog.csdn.net/weixin_65728526/article/details/135855205
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！