数据结构与算法---单调栈结构

---

 

1 滑动窗口问题

 

由一个代表题目，引出一种结构

【题目】

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4[3 5 4]3 3 6 7 窗口中最大值为5
4 3[5 4 3] 3 6 7 窗口中最大值为5
4 3 5[4 3 3] 6 7 窗口中最大值为4
4 3 5 4[3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n，窗口大小为w，则一共产生 n-w+1 个窗口的最大值。

请实现一个函数。 输入: 整型数组arr，窗口大小为w。

输出:一个长度为 n - w + 1的数组res，res[i] 表示每一种窗口状态下的最大值 以本题为例,结果应该
返回{5,5,5,4,6,7}

public class SlidingWindowMaxArrTest {

    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
        final int w = 3;
        int[] windowMaxArr = getWindowMaxArr(arr, w);
        for (int i = 0; i < windowMaxArr.length;i++){
            System.out.print(windowMaxArr[i] + " ");
        }
        System.out.println();
    }

    /**
     * @param arr
     * @param w   窗口的宽度
     * @return
     */
    public static int[] getWindowMaxArr(int[] arr, int w) {
        if (arr == null || arr.length < w || w < 1) {
            return null;
        }
        /**
         * 双端队列 存放数组的索引
         *  队列的头部存放最大值的索引
         */
        LinkedList<Integer> qMax = new LinkedList<>();
        // 滑动窗口最大值数组
        int[] retArr = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            // 放入队列的元素 要保证队列头部的值是最大的
            // 放入的时候发现队列的最后一个元素没有大于arr[i] 则 弹出
            while (!qMax.isEmpty() && arr[i] >= arr[qMax.peekLast()]) {
                qMax.pollLast();
            }
            qMax.addLast(i);
            // 队列中的头部的元素过期
            if (qMax.peekFirst() == i - w) {
                qMax.pollFirst();
            }
            if (i >= w - 1) {
                retArr[index++] = arr[qMax.peekFirst()];
            }
        }
        return retArr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

 

2 单调栈的结构和实现原理

 

在数组中想找到一个数，左边和右边比这个数小、且离这个数最近的位置。
如果对每一个数都想求这样的信息，能不能整体代价达到 $O(N)$ ？需要使用到单调栈结构

1. 数组中无重复的情况

coding

public class MonotonousStackTest {

    public static void main(String[] args) {
        int[] arr = {10,9,12,30,11,14};
        int[][] retArr = getNearBiggerNoRepeat(arr);
        for (int i = 0; i < retArr.length;i++){
            System.out.println(arr[i] + " : left " + (retArr[i][0] == -1 ? -1 : arr[retArr[i][0]]) +
                    " right " + (retArr[i][1] == -1 ? -1 : arr[retArr[i][1]]));
        }
    }

    /**
     * 获取数组中每个元素左边和右边比它大且离它最近的数
     * 数组中的元素 不重复
     * @param arr
     * @return
     * @brief (O^..^O)
     */
    public static int[][] getNearBiggerNoRepeat(int[] arr){
        if (arr == null || arr.length < 2){
            return null;
        }
        // 第一列存放左边比当前值大且离它最近
        // 第二列存放右边比当前值大且离它最近
        int [][] retArr = new int[arr.length][2];
        // 栈中的元素 从栈底到栈顶 从大到小 栈中存放的是索引
        Stack<Integer> stack = new Stack<>();
        for (int index = 0; index < arr.length;index++){
            while (!stack.isEmpty() && arr[index] > arr[stack.peek()]){ // 当前元素比栈中栈顶的元素大
                int topIndex = stack.pop();//栈顶元素弹出
                int leftIndex = stack.isEmpty() ? -1 : stack.peek();// 左边比当前数大且离它最近的数的索引
                retArr[topIndex][0] = leftIndex;
                retArr[topIndex][1] = index;
            }
            stack.push(index);
        }
        // 栈中还有元素
        while (! stack.isEmpty()){
           int topIndex = stack.pop();
           int leftIndex = stack.isEmpty() ? -1 : stack.peek();
           retArr[topIndex][0] = leftIndex;
           retArr[topIndex][1] = -1;//右边比它大的数没有
        }
        return retArr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

2. 数组中无重复的情况

   /**
     * @brief  获取数组中每个元素左边和右边比它大且离它最近的数
     * 数组中的元素可以重复
     *
     * @param arr
     * @return
     */
    public static int[][] getNearBiggerRepeat(int[] arr){
        if (arr == null || arr.length < 2){
            return null;
        }
        int[][] retArr = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int index = 0;index < arr.length;index++){
            while (!stack.isEmpty() && arr[index] > arr[stack.peek().get(0)]){
                List<Integer> topList = stack.pop();
                // 链表非空 则左边比当前值大 且离它最近的元素为 它底下的链表中的最后一个元素
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                for (Integer e : topList) {
                    retArr[e][0] = leftLessIndex;
                    retArr[e][1] = index;
                }
            }
            // 栈顶存放索引对应的值 和 当前数组的值 相等 则 加入原链表
            if (!stack.isEmpty() && arr[index] == arr[stack.peek().get(0)]){
                stack.peek().add(index);
            } else {
                List<Integer> indexList = new ArrayList<>();
                indexList.add(index);
                stack.push(indexList);
            }
        }
        while (! stack.isEmpty()) {
            List<Integer> topList = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            for (Integer e : topList) {
                retArr[e][0] = leftLessIndex;
                retArr[e][1] = -1;
            }
        }
        return retArr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

 

3 单调栈的应用

 

有一个正数数组,定义指标A : 数组中所有的元素的累加和与最小值的乘积
给定一个数组,请返回数组中指标A的最大值

为数组中的每一个元素作为最小值时,求出指标A的最大值

基于上述条件,如何求当元素 arr[i] 作为最小值时的子数组,需要求出 arr[i] 左边比它小且离它最近和 右边比它小且离它最近 这就是单调栈问题

 

先来一波暴力解法,清爽自然…

如下 :

/**
 * 找出数组所有子数组,求子数组中的最小值*子数组的累加和 
 * 数组中所有的数均为整数
 * 再求最大值
 * @param arr
 * @return
 */
public static int getAllTimesMinToMaxViolence(int[] arr){
    if (arr == null || arr.length < 1){
        return 0;
    }
    // 数组中出现小于 0 直接返回 0 
    for (int index = 0;index < arr.length;index ++){
        if (arr[index] < 0){
            return 0;
        }
    }
    
    int retMax = -1;
    
    for (int sIndex = 0;sIndex < arr.length;sIndex++){ // sIndex 子数组开始索引
        for (int eIndex = sIndex; eIndex < arr.length;eIndex++){ // 子数组结束索引
            int min = arr[sIndex];
            // 求解子数组的指标 A
            int sum = 0;
            for (int index = sIndex;index <= eIndex;index++){
               min = Math.min(min,arr[index]);
               sum += arr[index];
            }
            retMax = Math.max(retMax,sum * min);
        }
    }
    return retMax;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

 

/**
  * @param arr
  * @return
  */
 public static int getAllTimesMinToMax(int[] arr) {
     int arrLen = arr.length;
     if (arr == null || arrLen < 1) {
         return 0;
     }
     Stack<Integer> stack = new Stack<>();//栈中 元素  从栈底到栈顶 从小到大排列
     // 对于数组中的每一个元素 都求解 以这个元素作为最小的值 指标A的最大值
     int ret_maxVal = -1;
     // 数组中从0位置到index位置的所有元素的累加和
     int[] indexSumArr = new int[arr.length];
     indexSumArr[0] = arr[0];
     for (int index = 1; index < arrLen; index++) {
         indexSumArr[index] = indexSumArr[index - 1] + arr[index];
     }
     for (int index = 0; index < arr.length;index++){
         // 遇到了比栈顶小元素则可进行结算
         while (!stack.isEmpty() && arr[index] <= arr[stack.peek()]){
             int topIndex = stack.pop();
             // indexSumArr[index - 1] - indexSumArr[arr[stack.peek()]]
             //子数组元素为最小值时到(index - 1)的累加和
             ret_maxVal = Math.max(ret_maxVal,
                     (stack.isEmpty() ? indexSumArr[index - 1] : 
                             indexSumArr[index - 1] - indexSumArr[stack.peek()])
                             * arr[topIndex]);
         }
         stack.push(index);
     }

     while (!stack.isEmpty()){
         int topIndex = stack.pop();
         ret_maxVal = Math.max(ret_maxVal,  (stack.isEmpty() ? indexSumArr[arrLen - 1] :
                 indexSumArr[arrLen - 1] - indexSumArr[stack.peek()])
                 * arr[topIndex]);
     }
     return ret_maxVal;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41