双端队列

双端队列，代价都是O(1)，不需要这个结构表示第几个数是最大值，只需要双端队列可以依次增加或减少数值。
双端队列中每次保存两个值，当前的数值和当前的位置信息。
双端队列保存的是数在数组中的下标，通过下标不仅可以找到数组中对应的值，由于它是从小到大，可以用来当作过期时间

  • 加数的逻辑：
    1. 每次小的值从右边进入双端队列，整个队列形成从大到小排列的顺序。
    2. 如果出现新的数值大于最右边的小数值，则将小的数值弹出，直到放得下新的数值。为什么可以将小于当前数的值删除，因为当前数的过期时间大于队列里所有数的过期时间，而且它的值也大于队列中小于它的数，小于它的数再也没有可能成为最大值
    3. 如果出现相等的数值，则将先前的数值弹出，将新的数值保存
  • 减数的逻辑：
    1. L移动的时候，分析当前最大值所在的位置信息是否过期（最大值是否还在窗口里），如果过期则弹出，没过期则显示当前的最大值。

加数的逻辑中的原理解释：每次增加新的值的时候，如果新增的值比当前双端队列中保存的值小，则需要保留，因为窗口滑动过去之前的较大值之后后面现在的较小的值还有可能变成最大值。当新来了一个较大的值，比队列中的一些值大或相等，则可以直接将那些值删掉，因为接下来那些值存在的时候，新来的值一定存在，并且比那些值大，所以可以直接删掉。
对于双端队列，可以只保存下角标，然后从原始数组中去读取数据值。

滑动窗口求最大值

image.png

  1. public class SlidingWindowMaxArray {
  3.     public static int[] getMaxWindow(int[] arr, int w) {
  4.         if (arr == null || w < 1 || arr.length < w) {
  5.             return null;
  6.         }
  7.         LinkedList<Integer> qmax = new LinkedList<Integer>();
  8.         int[] res = new int[arr.length - w + 1];
  9.         int index = 0;
  10.         for (int i = 0; i < arr.length; i++) {
  11.             while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
  12.                 qmax.pollLast();
  13.             }
  14.             qmax.addLast(i);
  15.             if (qmax.peekFirst() == i - w) { // i - w 过期的下标
  16.                 qmax.pollFirst();
  17.             }
  18.             if (i >= w - 1) { // 窗口形成了
  19.                 res[index++] = arr[qmax.peekFirst()];
  20.             }
  21.         }
  22.         return res;
  23.     }
  25.     // for test
  26.     public static void printArray(int[] arr) {
  27.         for (int i = 0; i != arr.length; i++) {
  28.             System.out.print(arr[i] + " ");
  29.         }
  30.         System.out.println();
  31.     }
  33.     public static void main(String[] args) {
  34.         int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
  35.         int w = 3;
  36.         printArray(getMaxWindow(arr, w));
  37.     }
  38. }

单调栈结构

单调栈解决的问题是：

【单调递减栈】对于一个数组中每一个数，求左边离他近的比他大的和右边离他近的比他大的数；
【单调递增栈】对于一个数组中每一个数，求左边离他近的比他小的和右边离他近的比他小的数。
同时时间复杂度O(n)，单调减栈栈底到栈顶单调递减，从大到小，递增相反。
【分析】只分析单调减栈，单调增栈同理。（栈内只放下标，比较大小时只需由下标检索）
数组从左往右遍历，大的数放下面，如果遇到一个数比栈顶的数大，则栈顶的数出栈，此时他的右边最近比他大的数就是让他出栈的数，而他左边最近比他大的数就是他栈内下方紧挨着的那个数。
如果下方为空，则左边没有比他大的数；如果没有数让它出栈，说明数组遍历结束，右方没有比他大的数。
【ps】如果遇到连续相等的数，则把序号压在一起放入栈内（链表）。
【举例】5（0）4（1）3（2）6（3）后面括号代表所属位置。

  1. 5（0）压入栈然后4（1）比5（0）小，所以将4（1）压入栈中 第三步因为3（2）比4（1）小，所以也压入栈中
  2. 6（3）比3（2）要大，此时弹出栈顶的值3（2），并且将括号内的角标改成3变成3（3），代表对于3（2）这个数而言，右边第一个比他大的数位于3的位置。
  3. 3（2）左边离他最近的比他大的值就是在3的栈中的下一个值，也就是4（1）。
  4. 比较完之后将当前的6（3）放入数组之中，之前获得了信息的值可以直接进行表示了，不需要再放入栈中。
  5. 等到最后栈中还存在内容，则此时的所有数据单独弹出，此时右边没有比他大的数，栈中下面的数值是他的左边的比他大的数值。

  6. 如果出现相等数的情况，则此时下标压在一起，弹出是也一起弹出，多次计算。(链表实现)
    由于每个数都是进栈一次出栈一次，所以复杂度为O(N)。

    1. public class MonotonousStack {
    3.  public static int[][] getNearLessNoRepeat(int[] arr) {
    4.      int[][] res = new int[arr.length][2];
    5.      Stack<Integer> stack = new Stack<>();
    6.      for (int i = 0; i < arr.length; i++) {
    7.          while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
    8.              int popIndex = stack.pop();
    9.              int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
    10.              res[popIndex][0] = leftLessIndex;
    11.              res[popIndex][1] = i;
    12.          }
    13.          stack.push(i);
    14.      }
    15.      while (!stack.isEmpty()) {
    16.          int popIndex = stack.pop();
    17.          int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
    18.          res[popIndex][0] = leftLessIndex;
    19.          res[popIndex][1] = -1;
    20.      }
    21.      return res;
    22.  }
    24.  public static int[][] getNearLess(int[] arr) {
    25.      int[][] res = new int[arr.length][2];
    26.      Stack<List<Integer>> stack = new Stack<>();
    27.      for (int i = 0; i < arr.length; i++) {
    28.          while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
    29.              List<Integer> popIs = stack.pop();
    30.              // 取位于下面位置的列表中，最晚加入的那个
    31.              int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
    32.                      stack.peek().size() - 1);
    33.              for (Integer popi : popIs) {
    34.                  res[popi][0] = leftLessIndex;
    35.                  res[popi][1] = i;
    36.              }
    37.          }
    38.          if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
    39.              stack.peek().add(Integer.valueOf(i));
    40.          } else {
    41.              ArrayList<Integer> list = new ArrayList<>();
    42.              list.add(i);
    43.              stack.push(list);
    44.          }
    45.      }
    46.      while (!stack.isEmpty()) {
    47.          List<Integer> popIs = stack.pop();
    48.          // 取位于下面位置的列表中，最晚加入的那个
    49.          int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
    50.                  stack.peek().size() - 1);
    51.          for (Integer popi : popIs) {
    52.              res[popi][0] = leftLessIndex;
    53.              res[popi][1] = -1;
    54.          }
    55.      }
    56.      return res;
    57.  }
    59.  // for test
    60.  public static int[] getRandomArrayNoRepeat(int size) {
    61.      int[] arr = new int[(int) (Math.random() * size) + 1];
    62.      for (int i = 0; i < arr.length; i++) {
    63.          arr[i] = i;
    64.      }
    65.      for (int i = 0; i < arr.length; i++) {
    66.          int swapIndex = (int) (Math.random() * arr.length);
    67.          int tmp = arr[swapIndex];
    68.          arr[swapIndex] = arr[i];
    69.          arr[i] = tmp;
    70.      }
    71.      return arr;
    72.  }
    74.  // for test
    75.  public static int[] getRandomArray(int size, int max) {
    76.      int[] arr = new int[(int) (Math.random() * size) + 1];
    77.      for (int i = 0; i < arr.length; i++) {
    78.          arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
    79.      }
    80.      return arr;
    81.  }
    83.  // for test
    84.  public static int[][] rightWay(int[] arr) {
    85.      int[][] res = new int[arr.length][2];
    86.      for (int i = 0; i < arr.length; i++) {
    87.          int leftLessIndex = -1;
    88.          int rightLessIndex = -1;
    89.          int cur = i - 1;
    90.          while (cur >= 0) {
    91.              if (arr[cur] < arr[i]) {
    92.                  leftLessIndex = cur;
    93.                  break;
    94.              }
    95.              cur--;
    96.          }
    97.          cur = i + 1;
    98.          while (cur < arr.length) {
    99.              if (arr[cur] < arr[i]) {
    100.                  rightLessIndex = cur;
    101.                  break;
    102.              }
    103.              cur++;
    104.          }
    105.          res[i][0] = leftLessIndex;
    106.          res[i][1] = rightLessIndex;
    107.      }
    108.      return res;
    109.  }
    111.  // for test
    112.  public static boolean isEqual(int[][] res1, int[][] res2) {
    113.      if (res1.length != res2.length) {
    114.          return false;
    115.      }
    116.      for (int i = 0; i < res1.length; i++) {
    117.          if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
    118.              return false;
    119.          }
    120.      }
    122.      return true;
    123.  }
    125.  // for test
    126.  public static void printArray(int[] arr) {
    127.      for (int i = 0; i < arr.length; i++) {
    128.          System.out.print(arr[i] + " ");
    129.      }
    130.      System.out.println();
    131.  }
    133.  public static void main(String[] args) {
    134.      int size = 10;
    135.      int max = 20;
    136.      int testTimes = 2000000;
    137.      for (int i = 0; i < testTimes; i++) {
    138.          int[] arr1 = getRandomArrayNoRepeat(size);
    139.          int[] arr2 = getRandomArray(size, max);
    140.          if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
    141.              System.out.println("Oops!");
    142.              printArray(arr1);
    143.              break;
    144.          }
    145.          if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
    146.              System.out.println("Oops!");
    147.              printArray(arr2);
    148.              break;
    149.          }
    150.      }
    151.  }
    152. }

    定义：数组是一个正数数组，数组中累积和与最小值的乘积，假设叫做指标A。给定一个数组，请返回子数组中，指标A最大的值。

    每一个数字在它的子数组中是最小值 ```java import java.util.Stack;

public class AllTimesMinToMax {

public static int max1(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            int minNum = Integer.MAX_VALUE;
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += arr[k];
                minNum = Math.min(minNum, arr[k]);
            }
            max = Math.max(max, minNum * sum);
        }
    }
    return max;
}

public static int max2(int[] arr) {
    int size = arr.length;
    int[] sums = new int[size];
    sums[0] = arr[0];
    for (int i = 1; i < size; i++) {
        sums[i] = sums[i - 1] + arr[i];
    }
    int max = Integer.MIN_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < size; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            int j = stack.pop();
            max = Math.max(max, (stack.isEmpty() ? 
                                 sums[i - 1] : 
                                 (sums[i - 1] - sums[stack.peek()])) * arr[j]);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int j = stack.pop();
        max = Math.max(max, (stack.isEmpty() ? 
                             sums[size - 1] : 
                             (sums[size - 1] - sums[stack.peek()])) * arr[j]);
    }
    return max;
}

public static int[] gerenareRondomArray() {
    int[] arr = new int[(int) (Math.random() * 20) + 10];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 101);
    }
    return arr;
}

public static void main(String[] args) {
    int testTimes = 2000000;
    for (int i = 0; i < testTimes; i++) {
        int[] arr = gerenareRondomArray();
        if (max1(arr) != max2(arr)) {
            System.out.println("FUCK!");
            break;
        }
    }
}

}

```java
public class Test1 {

    public static class Employee {
        public int happy; // 这名员工可以带来的快乐值
        public List<Employee> nexts; // 这名员工有哪些直接下级
    }

    public static int maxHappy (Employee boss) {
        Info headInfo = process(boss);
        return Math.max(headInfo.laiMaxHappy, headInfo.buMaxHappy);
    }

    public static class Info {
        public int laiMaxHappy;
        public int buMaxHappy;
        public Info(int lai,int bu) {
            laiMaxHappy = lai;
            buMaxHappy = bu;
        }
    }

    public static Info process(Employee x) {
        if (x.nexts.isEmpty()) { // x是基层员工的时候
            return new Info(x.happy, 0);
        }

        int lai = x.happy; // x来的情况下，整棵树最大收益
        int bu = 0; // x不来的情况下，整棵树最大收益
        for (Employee next : x.nexts) {
            Info nextInfo = process(next);
            lai += nextInfo.buMaxHappy;
            bu += Math.max(nextInfo.laiMaxHappy, nextInfo.buMaxHappy);
        }
        return new Info(lai, bu);
    }
}