LeetCode-1944题： 队列中可以看到的人数（原创）

【题目描述】

        有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。

【题目链接】. - 力扣（LeetCode）

【解题代码】

package array;

import common.Utils;

import java.util.Arrays;
import java.util.Stack;

public class CanSeePersonsCount {

    public static void main(String[] args) {
        //int heights[] = {10, 6, 8, 5, 11, 9};
        //int heights[] = {5, 1, 2, 3, 10};
        int[] heights = Utils.readArrayFromFile("res\\1944\\40.txt");

        long start = System.currentTimeMillis();
        System.out.println("开始计算。。。");
        int[] result = canSeePersonsCount(heights);
        System.out.println("运行时长：" + (System.currentTimeMillis() - start) + "ms");
        System.out.println("计算结果:" + Arrays.toString(result));
    }

    public static int[] canSeePersonsCount(int[] heights) {
        int[] result = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(heights[heights.length - 1]);
        for (int i = heights.length - 2; i >= 0; i--) {
            result[i] = 1;
            while (heights[i] > stack.peek()) {
                stack.pop();
                if (!stack.empty())
                    result[i]++;
                else break;
            }
            stack.push(heights[i]);
        }
        return result;
    }

}

【解题思路】

拿到题目，一开始想到的最简单思路就是位置i从0开始向后查找，设置一个数值max，记录当前最大身高，目前位置的人是否能被看到，取决于当前位置身高是否小于观测者并且大于max（没被挡住）,一直轮询直到数值大于当前值的位置或者最后一个人为止，很快就完成代码编写

public int[] canSeePersonsCount1(int[] heights) {
    // 定义一个数组，记录所有位置能看到的人数
    int[] result = new int[heights.length];
    int max, j;
    for (int i = 0; i < heights.length - 1; i++) {
        // 从当前位置右边第一个位置开始计算
        j = i + 1;
        // 定义当前位置右边遍历的最大身高
        max = 0;
        // 向后依次轮询，直到数值大于当前值的位置为止
        do {
            // 如果当前位置身高大于当前最大身高，那么计数加1，并更新当前最大身高
            if (heights[j] > max) {
                result[i]++;
                max = heights[j];
            }
        } while (heights[j] < heights[i] && ++j < heights.length);
    }
    return result;
}

LeetCode试运行成果，看来逻辑正确，但这一道题毕竟是困难级别，这种两种循环的简单低级算法代码提交肯定不能通过，试了一下，果不其然，LeetCode系统报错：超出时间限制：

作为一个爱追根究底的程序员，我把LeetCode系统报错的测试用例的数据拷贝到一个文件里，然后，本地加载运行，看看到底需要运行多长时间，相关加载数据代码

public static int[] readArrayFromFile(String fileName) {
    StringBuffer sb = null;
    try {
        BufferedReader in = new BufferedReader(new FileReader(fileName));
        while (in.ready()) {
            sb = new StringBuffer(in.readLine());
        }
    } catch (Exception e) {
        return null;
    }

    String[] dataStrs = sb.toString().split(",");
    return Arrays.stream(dataStrs).mapToInt(Integer::parseInt).toArray();
}

本地执行一下，运行时长1656ms，肯定不合格。这只是简单热个身，接下来还是考虑专业的算法思路，看到代码页面下面有5个英文提示，翻译成中文如下：

1. 如何以二次复杂度解决这个问题？-- 啥叫二次复杂度，哥们要的是提示，不是提问！
2. 对于从索引 i 开始的每个子数组，不断查找新的最大值，直到找到大于 arr[i] 的值。--正确但无用的废话，以哥们的智商，这么简单的东西还要你来提示？
3. 由于限制很高，因此您需要线性解决方案。--又是正确但无用的废话
4. 当您从末尾到开头迭代数组时，使用堆栈来保持数组值的排序。--哎！堆栈！这个提示有搞头，继续看看下面怎么说。
5. 继续按排序顺序从堆栈中弹出元素，直到找到大于 arr[i] 的值，这些是我可以看到的值。--这句的意思好像是每次看到的人，都是从堆栈依次弹出，一直到大于当前位置身高值

根据后面两个稍微有用的提示，反复思考终于有了眉目，几点思路总结如下：

1. 最右一个人看到的人数是0，因为右边没人了；
2. 其它位置能看到的人数至少是1，右边至少能看到1个人
3. 其它位置向右看到的身高，肯定是一个比一个高，因为小于当前位置身高的，左边的人肯定看不到；
4. 先将最右的人身高压栈
5. 从最右边第二个位置开始，依次将栈中比当前身高矮的值出栈，然后将当前位置压栈
6. 当前栈顶是右边第一个人身高，后面肯定是一个比一个高

思路一打开，解题就简单了，且看下面解题步骤

【解题步骤】

1. 定义一个数组，记录所有位置能看到的人数

   int[] result = new int[heights.length];

2. 定义一个堆栈，记录当前位置身高以及其右边“一个比一个高”的身高

   Stack<Integer> stack = new Stack<>();

3. 将最右侧人身高压栈,最右侧的人看到的人数为0

   stack.push(heights[heights.length - 1]);

4.  从最右边第二个位置开始，依次计算能看到的人数，当前位置至少能看到右侧紧挨着的这个人

   for (int i = heights.length - 2; i >= 0; i--) {
       result[i] = 1;

5. 后从栈中弹出所有比当前位置身高矮的人，这些都是当前位置能看到的人，也都是左边位置都看不到的人

   while (heights[i] > stack.peek()) {
       stack.pop();
       if (stack.empty()) break;
       result[i]++;
   }

6. 再将当前位置身高压栈，栈里此时状况是"一山还比一山高"

   stack.push(heights[i]);

7. 最后返回结果

   return result;

【思考总结】

1. 专业深入的思考之前，可以简单的方式实现热热身；
2. LeetCode解题一个关键点就是，需要掌握相关调试工具和技巧，对于算法执行时间等性能指标要有清晰的数据；
3. 这道题算法设计的关键点在于使用堆栈：以及保存当前位置右侧所有的“一山还比一山高”的身高；
4. LeetCode解题之前，可以看提示，但一定不要看题解，看了就“破功”了！