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; }