[刷题]下一个更大元素问题

问题描述

对一个数组的每一个元素,找到当前位置之后第一个比当前元素大的元素
如 [2,1,3,4] ==[Next Greater Number Array]==> [3,3,4,-1]

解法思路

1.如果我们从前往后考虑这个问题,最直接的思路,对每个位置我们比较当前元素和之后所有元素,遇到第一个比自己大的,即为所求。这种暴力法的时间复杂度为O(N x N)
2.那么我们是否可以减少一些比较呢?当然是可以的,我们从后往前考虑这个问题。我们用一个有序栈保存比当前位置大的元素(并不是所有比当前大的)。如[2,1,4,3,6,7] 当遍历到1时栈为[4.6,7],也就是对于一个位置只能看到第一个比自己大的元素。遍历到一个元素时,比较栈顶元素和自己,比自己小的元素都被刨除(栈中比自己小的元素都弹出),直到栈顶元素比自己大,记录这个元素(或做一些相应的操作)。由于不知道下一个遍历的元素比自己大还是小,所以把自己也放入栈中,遍历下一个元素。

通用代码
public int[] NextGreaterNumber(int[] T) {  
    Stack<Integer> stack = new Stack<>();  
     int[] res = new int[T.length];  
     for(int i=T.length-1;i>=0;i--){  
        while (!stack.empty()&&stack.peek()<=T[i]){  
            stack.pop();  
        }  
        if(stack.empty()) res[i] = -1;  
        else {  
            res[i] = stack.peek();  
          }  
        stack.push(T[i]);  
  }  
    return res;  
}

相关题目

Leetcode 496/739/503/556

评论

暂无评论