大型网站制作报价,网站建设的售后服务流程,交互式网站是什么,企业网站开发用什么软件单调栈#xff1a;就是在栈中实现数据的单调性。即从栈底到栈顶#xff0c;要么递增#xff0c;要么递减。
那么#xff0c;使用单调栈#xff0c;可以解决什么问题呢#xff1f;
给定一个可能含有重复值的数组arr#xff0c;i位置的数一定存在如下两个信息
1#x…单调栈就是在栈中实现数据的单调性。即从栈底到栈顶要么递增要么递减。
那么使用单调栈可以解决什么问题呢
给定一个可能含有重复值的数组arri位置的数一定存在如下两个信息
1arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪
2arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪 如果想得到arr中所有位置的两个信息怎么能让得到信息的过程尽量快 题目一给定一个一维数组数据都为正整数并且无重复值要求设计一个ON时间复杂度的算法找出任意位置的数据左侧小于当前位置最近的数在哪右侧小于当前数最近的的数在哪 假设 这个数组是 {1,3,5,4}。栈的单调性从栈底到栈顶递增。
那么如下
531
也就是说前3个数符合预期的栈的单调性可以正常的放入栈中。那么当最后一个数据4想要放入栈中的时候发现栈顶元素为5比自己大。直接放入就破坏了栈的单调性了。
1. 我们需要把栈顶元素5弹出这5就知道右侧小于自己的并且距离最近的数为4而左侧离自己最近并且小于自己的数为3.
2. 此时栈顶元素为3小于4. 那么4直接放入栈顶。整个数组全部结束
431
3. 栈循环弹出4是最后一个元素并且栈具有单调性。因此弹出4可以知道左侧离自己最近的数为3. 而右侧没有比自己更小的数
4. 弹出3左侧比自己小的数是1而右侧没有比自己小的数
5. 弹出1此时栈空了。左侧、右侧都没有小于自己的数。
以上一切只是为了直观的体现栈整个操作流程。而实际的算法设计肯定是不能用数据来直接使用的而是需要使用每个数据对应的位置即下标
//无重复元素public int[][] dp(int[] arr){if(arr null || arr.length 0) {return null;}int[][] dp new int[arr.length][arr.length];StackInteger stack new Stack();for (int i 0; i arr.length; i){while (!stack.isEmpty() arr[stack.peek()] arr[i]){int cur stack.pop();// -1代表不存在左侧比cur下标对应的值更小的值int leftIndex stack.isEmpty() ? -1 : stack.peek();dp[cur][0] leftIndex;dp[cur][1] i;}//放入下标stack.push(i);}//栈中剩余元素保持单调增while (!stack.isEmpty()) {int cur stack.pop();// -1代表不存在左侧比cur下标对应的值更小的值int leftIndex stack.isEmpty() ? -1 : stack.peek();dp[cur][0] leftIndex;//因为单调增、所有右侧不存在比自己还小的值了dp[cur][1] -1;}return dp;}题目二数组存在重复元素设计一个栈要求能够快速找到任意位置左、右侧比自己小、位置最近的数据。
public static int[][] getNearLess(int[] arr) {int[][] res new int[arr.length][2];StackListInteger stack new Stack();for (int i 0; i arr.length; i) { // i - arr[i] 进栈while (!stack.isEmpty() arr[stack.peek().get(0)] arr[i]) {ListInteger 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 {ArrayListInteger list new ArrayList();list.add(i);stack.push(list);}}while (!stack.isEmpty()) {ListInteger 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;} 题目三力扣1856. 子数组最小乘积的最大值
https://leetcode.cn/problems/maximum-subarray-min-product/description/
题目详情直接打开连接进行查看这里直接说解题思路。
1. 给定数组就存在子数组并且子数组是连续的
2.子数组中肯定是存在最小值的也必然会知道子数组累加和。
3. 假设每个数都是最小值这样就能利用单调栈结构找到左侧、右侧比自己小的位置。那么除了这两个位置以外中间部分的数据就是自己最小了。利用这个思想我们来实现代码
数据1354下标0123累加和14913
5左侧比自己小的数据为3对应下标为1
5右侧比自己小的数据为4对应下标为3
也就是说5这个数据想要做最小值那么下标1到3之间并且不能包含下标1和下标3的和。
既然不能包含到下标为3的位置变相的也就是能够包含到下标为2的位置即累加和为 9 - 4 5
那子数组累加和 * 最小值 5 * 5 25
其他的依次类推........
package code04.单调栈_01;import java.util.Stack;/*** 1856. 子数组最小乘积的最大值* https://leetcode.cn/problems/maximum-subarray-min-product/description/*/
public class Code01_MinSumOfSubArr {public int maxSumMinProduct(int[] nums){if (nums null || nums.length 0) {return 0;}int size nums.length;//前缀和数组。 题目规定要使用64位有符号整数保存long[] dp new long[size];dp[0] nums[0];for (int i 1; i size; i) {dp[i] dp[i-1] nums[i];}long ans Long.MIN_VALUE;//[0 ......)StackInteger stack new Stack();for(int i 0; i size; i){while (!stack.isEmpty() nums[stack.peek()] nums[i]) {//当前正在处理的数下标int cur stack.pop();long sum stack.isEmpty() ? dp[i-1] : dp[i-1] - dp[stack.peek()];ans Math.max(ans, sum * nums[cur]);}//放入下标stack.push(i);}//右侧值越来越大while (!stack.isEmpty()) {//当前正在处理的数下标int cur stack.pop();long sum stack.isEmpty() ? dp[size-1] : (dp[size-1] - dp[stack.peek()]);ans Math.max(ans, sum * nums[cur]);}return (int) (ans % 1000000007);}public static void main(String[] args){int[] nums {3,1,5,6,4,2};Code01_MinSumOfSubArr test new Code01_MinSumOfSubArr();System.out.println(test.maxSumMinProduct(nums));}
}此处可能会有疑问此处使用的是无重复元素构造单调栈的算法这一题不需要考虑重复元素的情况吗举个例子假如数组为 {1,2,3,2}
栈中放入1,2 3. 当放入最后一个2的时候会把栈中的3和2弹出并且把最后一个2入栈。 而最后一个2右侧没有比他小的值左侧比他小的值为1对应的下标为0. 也就是说从下标0到最后一个2的位置此时最后一个2是最小值。当然下标0处的1是不包含在内的。
也就是说重复元素具有连通性很多时候是不需要考虑重复元素的情况的。
