Java-单调栈

怼烎@ 2023-10-09 18:36 1阅读 0赞

单调栈的作用是在一个数组中,求出离本元素最近的更小值(左边最小值和右边的最小值)

首先维护一个严格由小到大的栈结构

从头开始遍历数组

(1)如果此元素加入后不满足由小到大(此元素小于最上层元素)弹出最上层元素,直到满足由小到大为止,弹出一个值的时候使它弹出的元素就是它右边更小值,它的下一个就是左边更小值

(2)如果本元素和最上层相等,就把本元素和最上层元素"合并"

(3)如果比最上层元素大,直接加入

如果到最后所有元素都遍历完了栈中还有元素 只能说明此元素右侧没有更小值 如果一个元素在最底部被弹出说明它左侧没有更小值

public static int [][] MonotonousStack(int [] arr,int w) {
    	 Stack<List<Integer>> stack = new Stack<List<Integer>>();
    	 int [][] result = new int[arr.length][2];
    	 for(int i = 0;i<arr.length-1;i++) {
    		 while(!stack.empty()&&arr[i]>stack.peek().get(stack.peek().size() - 1)) {
    			 List<Integer> list = stack.pop();
    			 int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);//如果栈为空了说明下面没有数了
    				for (Integer popi : list) {
    					result[popi][0] = leftLessIndex;
    					result[popi][1] = i;
    				}
    		 }
    		 if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
    				stack.peek().add(Integer.valueOf(i));
    			} else {
    				ArrayList<Integer> list = new ArrayList<>();
    				list.add(i);
    				stack.push(list);
    			}//所以每一个list还是要自己初始化的
    	 }
    	 return result;
    }

(不可名状的注解是方便自己理解的...........)

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java-单调栈

单调栈的作用是在一个数组中,求出离本元素最近的更小值(左边最小值和右边的最小值) 首先维护一个严格由小到大的栈结构从头开始遍历数组 (1)如果此元素加入后不满足由小到大

怼烎@/ 2023年10月09日 18:36/ 0 赞/ 2 阅读

相关单调栈

> 参考https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaru

叁歲伎倆/ 2022年12月12日 13:58/ 0 赞/ 176 阅读

相关理解单调栈与单调队列

单调栈单调栈：栈内的元素按照某种方式排序下单调递增或单调递减，如果新入栈的元素破坏的单调性，就弹出栈内元素，直到满足单调性。单调栈分为单调递增栈和单调递减栈：

谁践踏了优雅/ 2022年10月08日 12:27/ 0 赞/ 222 阅读

相关单调栈，栈还能单调一下？

之前遇到一个算法题目，自己只会用时间复杂度 O(N^2) 暴力解法解决，有大佬说用单调栈，可以做到 O(N) 的时间复杂度，当时我的表情是这样的： ![1d3f60a4338

水深无声/ 2022年09月12日 11:59/ 0 赞/ 198 阅读

相关单调栈 - AcWing 830. 单调栈（C++）- 简单

题目链接：[https://www.acwing.com/problem/content/description/832/][https_www.acwing.com_prob

喜欢ヅ旅行/ 2022年08月28日 01:46/ 0 赞/ 223 阅读

相关单调栈

通过使用栈这个简单的结构，我们可以巧妙地降低一些问题的时间复杂度。单调栈性质： 1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素

ゝ一纸荒年。/ 2022年05月12日 07:28/ 0 赞/ 250 阅读

相关单调栈学习

学习可参考如下博客： [单调栈原理及应用详解附各种类型的题目练习][Link 1] 视频学习：[【算法讲堂】【电子科技大学】【ACM】单调队列与单调栈][ACM] 单

ゞ浴缸里的玫瑰/ 2022年02月22日 03:02/ 0 赞/ 266 阅读

相关单调栈学习总结

单调栈就是一个栈里面要么全放升序的值，要么全是降序的值。可以做下这道题加深理解：HDU 1506 [https://vjudge.net/problem/HDU-1506

浅浅的花香味﹌/ 2021年12月03日 02:49/ 0 赞/ 293 阅读

相关单调栈

单调栈性质单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。模型例如下图就是一个单调递增的单调栈。 ![

你的名字/ 2021年11月10日 12:46/ 0 赞/ 309 阅读

相关单调栈

一、单调栈定义单调递增栈：数据出栈的序列为单调递增序列（比站内元素小就入栈，否则将栈中比当前元素小的元素弹出后再入栈）单调递减栈：数据出栈的序列为单调递减

水深无声/ 2021年09月21日 05:40/ 0 赞/ 421 阅读