栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

单调栈(求最近的小于元素)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

单调栈(求最近的小于元素)

文章目录
  • 单调栈是什么?
  • 一、单调栈的实现
  • 相关题目
    • 1.子数组累加和乘以子数组最小值中的最大值
    • 2.柱状图中最大的矩形
    • [3.剑指 Offer II 040. 矩阵中最大的矩形](https://blog.csdn.net/xiaolu567/article/details/125211891)
    • [4.统计全 1 子矩形](https://blog.csdn.net/xiaolu567/article/details/125212087)
    • 5.子数组的最小值之和


单调栈是什么?

一种特别设计的栈结构,为了解决如下的问题:

给定一个可能含有重复值的数组arr,i位置的数一定存在如下两个信息
1)arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪?
2)arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪?
如果想得到arr中所有位置的两个信息,怎么能让得到信息的过程尽量快。

一、单调栈的实现

无重复数

如果加入的元素小于栈顶元素,则弹出栈顶元素,右侧最近小于元素为加入元素,左侧最近小于元素为栈顶元素的底下元素
最后单独结算栈,直到栈为空

	public static int[][] getNearLessNoRepeat(int[] arr) {
		int[][] res = new int[arr.length][2];
		// 只存位置!
		Stack stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) { // 当遍历到i位置的数,arr[i]
			while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
				int j = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
				res[j][0] = leftLessIndex;
				res[j][1] = i;
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int j = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
			res[j][0] = leftLessIndex;
			res[j][1] = -1;
		}
		return res;
	}

有重复数
用链表记录重复出现的元素,如果要弹出,统一结算链表里面的所有位置

	public static int[][] getNearLess(int[] arr) {
		int[][] res = new int[arr.length][2];
		Stack> stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
			while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
				List popIs = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
				for (Integer popi : popIs) {
					res[popi][0] = leftLessIndex;
					res[popi][1] = i;
				}
			}
			if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
				stack.peek().add(Integer.valueOf(i));
			} else {
				ArrayList list = new ArrayList<>();
				list.add(i);
				stack.push(list);
			}
		}
		while (!stack.isEmpty()) {
			List popIs = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
			for (Integer popi : popIs) {
				res[popi][0] = leftLessIndex;
				res[popi][1] = -1;
			}
		}
		return res;
	}
相关题目 1.子数组累加和乘以子数组最小值中的最大值 2.柱状图中最大的矩形 3.剑指 Offer II 040. 矩阵中最大的矩形 4.统计全 1 子矩形 5.子数组的最小值之和
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/964815.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号