一个数组中，我要求 每个位置左边离它最近的比它小的数在哪， 右边离它最近的比它小的数在哪
理解了怎么求最小的， 那么求最大的就知道怎么搞了，就反一下呗

image.png

  • 暴力解是O(N^2)的
    • image.png

流程（无重复值）

现在来看单调栈

先假设数组中是没有重复值的，理解了之后，再来看有重复值该怎么做

image.png

image.png
现在2位置的2要进栈了，因为要维持从栈底到栈顶从小到大，所以栈里的东西要弹出

注意：什么时候生成记录？ 当自己要从栈里弹出的时候生成记录

所以现在从栈里弹出1位置的4， 生成记录，
右边离1位置的最近的比他小的数是谁？ 就是此时此刻这个迫使他从栈里面弹出的这个数———> 也就是2位置的2，
那么左边离1位置的最近的比他小的数呢？
他在栈里面底下紧压着的是谁就是左边离他的最近的比他小的数 ——-> 也就是0位置的3
image.png
接下来2位置的2能进去嘛？不能。所以0位置的3弹出
image.png
现在2位置的2可以进去了
image.png
image.png
image.png
image.png
轮到5位置的0要进栈了，那么就会生成一批记录
image.png
image.png

整个数组遍历完后，单独处理栈中剩下的数

image.png

  1.  public static int[][] getNearLessNoRepeat(int[] arr) {
  2.         int[][] res = new int[arr.length][2];
  3.         Stack<Integer> stack = new Stack<>();
  4.         for (int i = 0; i < arr.length; i++) {
  5.             while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
  6.                 int popIndex = stack.pop();
  7.                 int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
  8.                 res[popIndex][0] = leftLessIndex;
  9.                 res[popIndex][1] = i;
  10.             }
  11.             stack.push(i);
  12.         }
  13.         while (!stack.isEmpty()) {
  14.             int popIndex = stack.pop();
  15.             int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
  16.             res[popIndex][0] = leftLessIndex;
  17.             res[popIndex][1] = -1;
  18.         }
  19.         return res;
  20.  }

原理

why？
比如a的底下压着b， C的出现要让a弹出， 这代表什么呢？

  • 首先a为什么会压着b？ —-> b一定比a小， b一定比a早进栈
  • 为什么C要让a弹出，说明c比a小

image.png
image.png

当这种情况，a要弹出的时候，为什么可以说C就是a右边离他最近的比他小的数， b就是a左边离他最近的比他小的数？

  • 证明：
    • 如果a…c 之间有一些数，那么这些数不会比a小，否则就不会轮到c来让a弹出了（数组中无重复值的情况）
      • 所以c就是右边离a最近的比a小的数
    • 如果b…a之间有一些数，
      • 1）这些数不会比b小，否则就不会轮到b来跟a做邻居了（b就会被这些数释放掉）
      • 2）这些数有没有可能 b< ? < a
        • 不可能，这样的话a和b中间会夹着一个数， 让a和b做不了邻居
        • image.png
      • 3） 那么就只剩一种可能性了， 这些数 > a
        • 所以b就是a左边最近的比a小的数，

流程（有重复值）

前面都是基于数组中无重复值整个假设来搞得，
现在我们来看如果数组中有重复值该咋办
流程会变
image.png
image.png
image.png
现在5位置得3要进栈了，底下得{3，4} —-> 4要释放，怎么释放呢？

  • image.pngimage.png

    总结一下，当一个数要出栈时怎么记录，右边离它最近比他小的就是那个让他出栈得那个数 左边离他最近比他小的就是底下紧压着得list中得最后一个下标

  • 思考一个问题，两个数怎么样才会贴在一起（结婚）

    • 两个数值相同，然后这两个数中间的数要么没有，要么都比他俩大
    • image.png
    • image.png
    • 接下来5位置的3要进栈了，那么会让底下的数都释放，然后和最底下的0位置的3结婚
    • image.png

    • 再看这个例子

    • image.png

      • 0位置7位置13位置都是3， 假设现在14位置的1来了，
      • 我们已经知道了结婚在一起的，它们两两之间隔的数要么没有，要么只会比它们大， 那么14位置的1就是这3个数右边的最近的比它们小的答案， 是这三个数总体的答案

      • 这3个结婚的底下压着的数就是左边的最近的比它们小的答案， 是这三个数总体的答案

      • 所以数组中有重复值的情况也是O(n)能拿下的

    • 最后别忘了遍历完数组后，如果栈里面还剩下东西，那么剩下的东西要结算，
  1. // 数组中有重复值
  2.     public static int[][] getNearLess(int[] arr) {
  3.         int[][] res = new int[arr.length][2];
  4.         Stack<List<Integer>> stack = new Stack<>();
  5.         for (int i = 0; i < arr.length; i++) {
  6.             while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
  7.                 List<Integer> popIs = stack.pop();
  8.                 int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
  9.                 for (Integer popI : popIs) {
  10.                     res[popI][0] = leftLessIndex;
  11.                     res[popI][1] = i;
  12.                 }
  13.             }
  14.             // 相等、比你小的
  15.             if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
  16.                 stack.peek().add(i);
  17.             } else {
  18.                 List<Integer> list = new ArrayList<>();
  19.                 list.add(i);
  20.                 stack.push(list);
  21.             }
  22.         }
  23.         while (!stack.isEmpty()) {
  24.             List<Integer> popIs = stack.pop();
  25.             int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
  26.             for (Integer popI : popIs) {
  27.                 res[popI][0] = leftLessIndex;
  28.                 res[popI][1] = -1;
  29.             }
  30.         }
  31.         return res;
  32.     }