单调栈专题

单调栈应用场景：一个近乎增序的数组，找到某个元素右边第一个小于它的元素。

单调栈简单题

hw

 * 给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，
 * 对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素
 * （如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。
 * 示例：
 * 输入: 5,  3,  1,  2,  4
 * 输出: -1  3  1  1  -1
1
2
3
4
5
6

思路：遍历数组，维护从栈底到栈顶递减的单调栈，循环查看如果有元素值大于栈顶元素，则输出数组的对应位置是这两个元素的间隔步数，并且栈顶元素出栈，为了记录步数方便，栈里存放数组的下标。
示例的步骤：
返回数组与给定数组长度相同，默认每个位置元素为-1
5的下标入栈 [5]
3的下标入栈 [5 > 3]
1的下标入栈 [5 > 3 > 1]
2大于栈顶对应的元素1,1对应的下标出栈，返回数组的元素1对应位置赋值为二者的步数间隔 [5 > 3]
2的下标入栈 [5 > 3 > 2]
4大于栈顶对应的元素2,2对应的下标出栈，返回数组的元素2对应位置赋值为二者的步数间隔 [5 > 3]
4大于栈顶对应的元素3,3对应的下标出栈，返回数组的元素3对应位置赋值为二者的步数间隔 [5]
4入栈 [5 > 4]

package com.athome.demo;

import java.util.Arrays;

// 暴力
public class Solution3 {
    public static int[] walk(int [] a) {
        int length = a.length;
        int [] b = new int[length];
        for (int i = 0; i < length; i++) {
            int j = i+1;
            while(j < length) {
                if (a[j] > a[i]) {
                    b[i] = j-i;
                    break;
                }
                j++;
            }
            if(j == length) {
                b[i] = -1;
            }
        }
        return b;
    }

// 单调栈
    public static int[] walk2(int[] a){
        int length = a.length;
        int[] b = new int[length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++){
            b[i] = -1;
            while(!stack.isEmpty() && a[i] > a[stack.peek()]) {
                b[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return b;
    }
    
    public static void main(String[] args) {
        int [] a = new int [] {5,  3,  4,  2,  4};

        int [] b = walk(a);
        for(int i = 0; i< b.length; i++) {
            System.out.println(b[i]);
        }
        System.out.println(Arrays.toString(b));
    }
}
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
48
49
50
51

力扣
155 最小栈
739 每日温度
1475 商品折扣后的最终价格
496 下一个更大元素 I
503 下一个更大元素 II : 循环数组

以下未做：
接雨水
84 柱状图中最大的矩形
1124 表现良好的最长时间段
和上面题目的思路类似的

Java打印数组的方法

1 Arrays.asList()
将数组转换成List，不适合打印存放基本数据类型的数组，

    public static void main(String[] args) {
        int[] arr = new int[]{0,1,2,3,4,5,6,7,8,9};
        System.out.println(Arrays.asList(arr));
        //打印结果：[[I@140e19d]
    }
1
2
3
4
5

Arrays.asList()可以打印基本数据类型的封装类

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{0,1,2,3,4,5,6,7,8,9};
        System.out.println(Arrays.asList(arr));
        //打印结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
1
2
3
4
5

2 使用 Arrays.toString() 或 Arrays.deepToString()
对于一维数组，可以使用Arrays.toString()方法，它支持将任意类型的数组转换为字符串

public static void main(String[] args) {
    int[] arr = new int[]{0,1,2,3,4,5,6,7,8,9};
    //使用Array.toString()
    System.out.println(Arrays.toString(arr));
    //打印结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
}
1
2
3
4
5
6

但对于多维数组，用 Arrays.toString() 就会出现和直接打印数组变量名时一样的问题，打印出来的是地址值。这时候，就需要使用 Arrays.deepToString() 方法来打印多维数组
(Java不会去使用多维数组，最多用到二维，因为Java会用到面向对象)

public static void main(String[] args) {
    int[][] arr = new int[][] {{1,2},{2,3},{3,4},{4,5},{5,6}};// 二维数组
    //使用Arrays.deepToString()
    System.out.println(Arrays.deepToString(arr));
}
	//打印结果：[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
1
2
3
4
5
6

3 使用 for 循环逐个元素打印