2016年10月6日星期四

First Smallest Number After Self

1.给一个int[]nums,返回int[] ans, ans[i]是i右边第一个小于等于nums[i]的数字,如果不存在,ans[i]=0

2.算法:
用一个stack维护单调递减
每个元素只出栈1次因此是线性

维护stack/queue思想的一道题: Sliding Window Maximum

 public static int[] firstRightSmallEqual(int[] nums){  
           Stack<Integer> stack = new Stack<>();  
           int[] ans = new int[nums.length];  
           for(int i = nums.length-1;i>=0; i--){  
                while(!stack.empty() && nums[stack.peek()] > nums[i]){  
                     stack.pop();  
                }  
                if(!stack.empty()) ans[i] = nums[stack.peek()];  
                stack.push(i);  
           }  
           return ans;  
      }  

没有评论:

发表评论