1762. Buildings With an Ocean View

My first solution is use two skacks, one stack store index, another one store value, the time complexity is O(n).

    public int[] findBuildings(int[] heights) {
        Stack<Integer> indexStk = new Stack<>();
        Stack<Integer> valueStk = new Stack<>();
        for(int i=heights.length-1;i>=0;i--){
            if(valueStk.isEmpty() || heights[i]>valueStk.peek()){
                indexStk.push(i);
                valueStk.push(heights[i]);
            }
        }
        int[] res = new int[indexStk.size()];
        int i=0;
        while(!indexStk.isEmpty()){
            res[i++]=indexStk.pop();
        }
        return res;
    }

The second stack, valueStk, can be replaced with an Integer.

    public int[] findBuildings(int[] heights) {
        int n = heights.length;
        Stack<Integer> indexStk = new Stack<>();
        int valueStk = heights[n-1];
        indexStk.push(n-1);
        for(int i=n-2;i>=0;i--){
            if(heights[i]>valueStk){
                indexStk.push(i);
                valueStk = heights[i];
            }
        }
        int[] res = new int[indexStk.size()];
        int i=0;
        while(!indexStk.isEmpty()){
            res[i++]=indexStk.pop();
        }
        return res;
    }

 

上一篇:promise等待多个异步请求完毕后再执行其他代码的方法


下一篇:136. 只出现一次的数字