如何加强省市网站建设,个人建设网站流程,wordpress图片托管,上海专业网站开发文章目录 题目思路分析代码实现 题目
给定一个不含有重复值的数组arr#xff0c;找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置#xff0c;返回所有位置相应的消息。 比如arr{3#xff0c;4#xff0c;1#xff0c;5#xff0c;6#xff0c;2#xff0c;… 文章目录 题目思路分析代码实现 题目
给定一个不含有重复值的数组arr找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置返回所有位置相应的消息。 比如arr{3415627}返回如下二位数组作为结果{[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]} -1表示不存在比如arr中0位置的左边没有元素所以是-1.右边最小的是1这个数据位置也就是index2所以得到{-12}。
如果我给定是一个可能含有重复值的数组arr呢
要求时间复杂度为O(N)。
思路分析
如果是时间复杂度为O(N2)的那么我们直接暴力解决即可都是如果这样子做这道题肯定就g了。
我们先来分析无重复的数组的情况。
原问题 准备一个栈记为 StackInteger栈中放的元素是数组的位置开始时stack 为空。如果找到每一个i位置左边和右边离i位置最近且值比 arrli]小的位置那么需要让stack 从栈顶到栈底的位置所代表的值是严格递减的如果找到每一个i位置左边和右边离i位置最近且值比 arr[i]大的位置那么需要让 stack 从栈顶到栈底的位置所代表的值是严格递增的。 本题需要解决的是前者但是对于后者,原理完全是一样的。
下面用例子来展示单调栈的使用和求解流程初始时 arr {3,4,1,5,6,2,7}stack 从栈顶到栈底为{}
遍历到arr[0]3发现stack为空就直接放入0位置。stack 从栈顶到栈底为:{0位置(值是3))
遍历到arr[1]4发现直接放入1位置,不会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的那么直接放入。stack从栈顶到栈底依次为:(1位置(值是4)、0位置(值是3)
遍历到arr[2]1发现直接放入2位置值是1)会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的所以从 stack开始弹出位置。如果x位置被弹出在栈中位于x位置下面的位置就是x位置左边离x位置最近且值比 arr[x]小的位置 当前遍历到的位置就是x位置右边离x位置最近且值比 arr[x]小的位置。 从 stack弹出位置1,在栈中位于1位置下面的是位置0,当前遍历到的是位置2所以 ans[1](0.2}。 弹出1位置之后发现放入2位置值是1)还会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的所以继续弹出位置0。 在栈中位于位置0下面已经没有位置了说明在位置О左边不存在比 arr[0]小的值当前遍历到的是位置2所以ans[0](-1,2}。stack 已经为空所以放入2位置值是1)stack从栈顶到栈底为:{2位置(值是1));
遍历到 arr[3]5发现直接放入3位置不会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的那么直接放入。stack 从栈顶到栈底依次为:3位置(值是5)、2位置(值是1);
遍历到 arr[4]6发现直接放入4位置不会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的那么直接放入。stack从 栈顶到栈底依次为:{(4位置(值是6)、3位置(值是5)、2位置(值是1);
遍历到 arr[5]2发现直接放入5位置会破坏stack从栈顶到栈底的位置所代表的值是严格递减的所以开始弹出位置。弹出位置4,栈中它的下面是位置3,当前是位置5, ans[4](3,5}。弹出位置3栈中它的下面是位置2当前是位置5ans[3](2,5}。然后放入5位置就不会破坏stack的单调性了。stack从栈顶到栈底依次为:{5位置(值是2)、2位置(值是1)};
遍历到arr[6]7发现直接放入6位置不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的那么直接放入。stack从栈顶到栈底依次为:{6位置(值是7)、5位置(值是2)、2位置(值是1)}。
遍历阶段结束后,清算栈中剩下的位置。
弹出6位置栈中它的下面是位置56位置是清算阶段弹出的所以 ans[6]{5,-1];弹出5位置栈中它的下面是位置25位置是清算阶段弹出的所以 ans[5]{2,-1];弹出2位置栈中它的下面没有位置了2位置是清算阶段弹出的所以 ans[2](-1,-1]。
至此已经全部生成了每个位置的信息。
我们可以按照上面的流程写出如下的代码 public static int[][] monotonicStackNorepeat(int[] arr) {StackInteger stack new Stack();int[][] res new int[arr.length][2];for (int i 0; i arr.length; i) {//如果当前栈不为空并且当前值比栈顶对应的元素小//那么就开始出栈 因为这说明栈内元素遇到了比自己小的数据了//并且一直出栈直到栈顶元素比当前元素小while (!stack.isEmpty() arr[stack.peek()] arr[i]) {//出栈得到栈顶元素对应的索引int popIndex stack.pop();//判断栈顶元素的左边是否还有元素 如果有 那么比栈顶元素的左边最小就是这个元素int leftLessIndex stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] leftLessIndex;//比栈顶元素右边小的元素的位置为ires[popIndex][1] i;}//放入当前元素 开启新一轮循环stack.push(i);}//清算阶段 对于还在栈中的元素while (!stack.isEmpty()) {//取出当前元素对应的索引位置int popIndex stack.pop();//判断是否他们的左边还有值左边的值都是比他们小的值int leftLessIndex stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] leftLessIndex;//清算阶段还在栈中说明他们的右边都是比他们大的或者就是已经没有后面的元素了res[popIndex][1] -1;}return res;}对于进阶问题她的情况是可能出现重复的数据但是大体的解答流程差不多思路如下
进阶问题可能含有重复值的数组如何使用单调栈。其实整个过程和原问题的解法差不多。举个例子来说明初始时 arr{3,1,3,4,3,5,3,2,2]stack从栈顶到栈底为{}
遍历到 arr[0]3发现stack为空就直接放入0位置。stack 从栈顶到栈底为:{0位置(值是3}
遍历到arr[1]1从栈中弹出位置0,并且得到ans[0][-1,1}。位置1进栈stack从栈顶到栈底为:{1位置(值是1)};
遍历到arr[2]3发现位置2可以直接放入。stack从栈顶到栈底依次为:{2位置(值是3).1位置(值是1)};
遍历到 arr[3]4发现位置3可以直接放入。stack从栈顶到栈底依次为:{3位置(值是4)、2位置(值是3)、1位置(值是1)};
遍历到arr[4]3从栈中弹出位置3并且得到ans[3]{2,4}。此时发现栈顶是位置2值是3当前遍历到位置4值也是3所以两个位置压在一起。stack 从栈顶到栈底依次为:{2位置,4位置、1位置(值是1)};
遍历到arr[5]5发现位置5可以直接放入。stack 从栈顶到栈底依次为:{5位置(值是5)、2位置,4位置、1位置(值是1));
遍历到arr[6]3从栈中弹出位置5在栈中位置5的下面是[2位置,4位置]选最晚加入的4位置当前遍历到位置6所以得到 ans[5]{4,6}。位置6进栈发现又是和栈顶位置代表的值相等的情况所以继续压在一起stack 从栈顶到栈底依次为:{2位置,4位置,6位置、1位置(值是1)};
遍历到arr[7]2从栈中弹出[2位置,4位置,6位置],在栈中这些位置下面的是1位置当前是7位置所以得到ans[2](1,7]、ans[4](1,7]、ans[6]{1,7}]。位置7进栈stack 从栈顶到栈底依次为:{7位置(值是2)、1位置(值是1)};
遍历到arr[8]2发现位置8可以直接进栈并且又是相等的情况stack从栈顶到栈底依次为:{7位置,8位置、1位置(值是1)}。
遍历完成后开始清算阶段:
弹出[7位置,8位置],生成ans[7]{1,-1]、ans[8]{1,-1};弹出1位置生成ans[1]{-1,-1}。
完整代码贴在下面
代码实现
package com.base.learn.stack;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;/*** author: 张锦标* date: 2023/5/28 11:00* MonotonicStack类* 单调栈题目*/
public class MonotonicStack {public static int[][] violentSolution(int[] arr) {int[][] res new int[arr.length][2];for (int i 0; i arr.length; i) {int leftMin -1;int rightMin -1;int cur i - 1;while (cur 0) {if (arr[cur] arr[i]) {leftMin cur;break;}cur--;}cur i 1;while (cur arr.length) {if (arr[cur] arr[i]) {rightMin cur;break;}cur;}res[i][0] leftMin;res[i][1] rightMin;}return res;}public static int[][] monotonicStackNorepeat(int[] arr) {StackInteger stack new Stack();int[][] res new int[arr.length][2];for (int i 0; i arr.length; i) {//如果当前栈不为空并且当前值比栈顶对应的元素小//那么就开始出栈 因为这说明栈内元素遇到了比自己小的数据了//并且一直出栈直到栈顶元素比当前元素小while (!stack.isEmpty() arr[stack.peek()] arr[i]) {//出栈得到栈顶元素对应的索引int popIndex stack.pop();//判断栈顶元素的左边是否还有元素 如果有 那么比栈顶元素的左边最小就是这个元素int leftLessIndex stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] leftLessIndex;//比栈顶元素右边小的元素的位置为ires[popIndex][1] i;}//放入当前元素 开启新一轮循环stack.push(i);}//清算阶段 对于还在栈中的元素while (!stack.isEmpty()) {//取出当前元素对应的索引位置int popIndex stack.pop();//判断是否他们的左边还有值左边的值都是比他们小的值int leftLessIndex stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] leftLessIndex;//清算阶段还在栈中说明他们的右边都是比他们大的或者就是已经没有后面的元素了res[popIndex][1] -1;}return res;}public static int[][] monotonicStackRepeat(int[] arr) {StackListInteger stack new Stack();int[][] res new int[arr.length][2];for (int i 0; i arr.length; i) {//如果当前栈不为空并且当前值比栈顶对应的元素小//那么就开始出栈 因为这说明栈内元素遇到了比自己小的数据了//并且一直出栈直到栈顶元素比当前元素小while (!stack.isEmpty() arr[stack.peek().get(0)] arr[i]) {//出栈得到栈顶元素对应的索引ListInteger popList stack.pop();//判断栈顶元素的左边是否还有元素 如果有 那么比栈顶元素的左边最小就是这个元素int leftLessIndex stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);for (Integer popi : popList) {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{//栈为空 或者当前元素与栈顶元素不一样 那么直接创建一个新的listArrayListInteger list new ArrayList();list.add(i);stack.push(list);}}//清算阶段 对于还在栈中的元素while (!stack.isEmpty()) {//出栈得到栈顶元素对应的索引ListInteger popList stack.pop();//判断栈顶元素的左边是否还有元素 如果有 那么比栈顶元素的左边最小就是这个元素int leftLessIndex stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);for (Integer popi : popList) {res[popi][0]leftLessIndex;res[popi][1] -1;}}return res;}public static void main(String[] args) {System.out.println(Arrays.deepToString(monotonicStackNorepeat(new int[]{3,4,1,5,6,2,7})));}
}
