2、Leetcode1019. 链表中的下一个更大节点(单调栈)

    参见《链表：与其它数据结构的结合》

3、LeetCode739. 每日温度(单调栈)

       请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

	public int[] dailyTemperatures(int[] T) {Stack   stack = new Stack();int [] ans = new int[T.length];for(int i = 0; i < T.length; i++){while(!stack.isEmpty() && T[i] > T[stack.peek()]){int day = stack.pop();ans[day] = i - day;}stack.push(i);}return ans;}

4、LeetCode901. 股票价格跨度(单调栈)

       编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：
输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

1. 调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
2. 每个测试用例最多可以调用  10000 次 StockSpanner.next。
3. 在所有测试用例中，最多调用 150000 次 StockSpanner.next。
4. 此问题的总时间限制减少了 50%。

算法：
1、根据题意需要求出比当前元素小的之前的元素个数，需要维护一个单调递减栈，当新元素大于栈顶元素时将其弹出
1、当新元素大于等于栈顶元素价格时将其弹出，直至小于栈顶元素值为止
2、向栈中压入一个价格为：max+1 的价格，保证栈永远不为空
3、价格跨度等新元素所在天数 - 栈顶元素所在天数。

class StockSpanner {class StockPrice{private int price;private int dayNum;public StockPrice(int price,int dayNum){this.price = price;this.dayNum = dayNum;}public int getPrice(){return price;}public int getDayNum(){return dayNum;}}private Stack stack = null;private int dayCnt = 0;public int MAX_PRICE = 100000;public int MIN_PRICE = 1;public StockSpanner() {stack = new Stack();stack.push(new StockPrice(MAX_PRICE+1,dayCnt));}public int next(int price) {if(price > MAX_PRICE || price < MIN_PRICE){return 0;}dayCnt++;while(price >= stack.peek().getPrice()){stack.pop();}int ans = dayCnt - stack.peek().getDayNum();stack.push(new StockPrice(price,dayCnt));return ans;}
}

5、LeetCode503. 下一个更大元素 II(单调栈)

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

算法：处理循环数组，将原始数组翻倍，使得每个元素都能看到整个数组的“全貌”。

5.1、正向遍历

算法：
1、初始化输出数组为-1；
2、正向遍历nums，维护单调递减栈，新元素nums[index]大于栈顶元素，弹栈操作并记录栈顶元素的下一个最大元素为新元素nums[index]
3、再次遍历保证数组 "末尾" 较小的元素能够被数组前面的较大元素"弹出"

	public int[] nextGreaterElements(int[] nums) {if(nums == null){return null;}Stack  stack = new Stack();int [] ans = new int[nums.length];Arrays.fill(ans,-1);for(int i = 0; i < nums.length*2; i++){int index = i % nums.length;while(!stack.isEmpty() && nums[index] > nums[stack.peek()]){ans[stack.pop()] = nums[index];}stack.push(index);}return ans;}

5.2、反向遍历

算法：
1、反向遍历数组nums，维护单调递减栈
2、当元素nums[i]大于等于栈顶元素时，直接弹出栈中元素，直到小于栈顶元素为止，此时栈顶元素就是新元素nums[index]的下一个最大值
3、当栈元素为空时，表示新元素nums[index]后面没有更大的元素
4、再次遍历保证数组 "末尾" 较小的元素能够看见数组前面的较大元素，因为此时较大元素已经在栈中(第一次遍历)

	public int[] nextGreaterElements(int[] nums) {if(nums == null){return null;}Stack  stack = new Stack();int [] ans = new int[nums.length];for(int i = nums.length*2 - 1; i >=0; i--){int index = i % nums.length;while(!stack.isEmpty() && nums[index] >= nums[stack.peek()]){stack.pop();}if(!stack.isEmpty()){ans[index] = nums[stack.peek()];}else{ans[index] = -1;}stack.push(index);}return ans;}

6、LeetCode556. 下一个更大元素 III

       给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例 1:
输入: 12
输出: 21示例 2:
输入: 21
输出: -1

算法：
1、从低位到高位（从右至左）逐个判断数字是逆序
Y:返回-1，此时index=0;
N:找到第一个升序点nums[index-1]< nums[index]
2、选取升序点右侧nums[index...length-1]第一个大于nums[index-1]的值，两者交换，注意：此时升序点右侧为降序排列
3、将升序点右侧nums[index...length-1]进行逆序，因为此时右侧为降序排列，逆序后从小到大为最小值

6.1、字符串处理

      public int nextGreaterElement(int n) {char []nums = (""+n).toCharArray();int index = nums.length-1;while(index > 0 && nums[index - 1] >= nums[index]){//找出第一个升序点index--;}if(index == 0){//数字降序return -1;}int j = nums.length -1;while(nums[j] <= nums[index - 1]){//找出升序点右侧第一个大于升序点值j--;}swap(nums,j,index - 1);//交换后，右侧认为降序排列reverse(nums,index,nums.length-1);//反转为升序try{return Integer.parseInt(new String(nums));}catch(Exception e){return -1;}}

6.2、分离数值n的位数

	public int nextGreaterElement(int n) {int number = n;int bitCnt = 0;int []nums = new int[20];//32位整数不会超过20位do{nums[bitCnt++] = number%10;number /= 10;}while(number != 0);int index = 0;while(index < nums.length - 1 && nums[index + 1] >= nums[index]){//高位大于低位继续index++;}if(index == nums.length - 1){return -1;}int j=0;while(nums[j] <= nums[index+1]){j++;}swap(nums,index+1,j);//此时低位到高位升序reverse(nums,0,index);//翻转为降序输出int newNumber = 0;for(int i = bitCnt -1; i >= 0; i--){newNumber = newNumber*10 + nums[i];}if(newNumber > n){return newNumber;}else{return -1;//新数可能溢出}}private void reverse(int []nums,int start,int end){while(start < end){swap(nums,start,end);start++;end--;}}private void swap(int []nums,int i,int j){int tmp = nums[j];nums[j] = nums[i];nums[i] = tmp;}

7、LeetCode31. 下一个排列（字节面试题）

        实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

算法：同上文的 LeetCode556，

	public void nextPermutation(int[] nums) {int index = nums.length - 1;while(index > 0 && nums[index-1] >= nums[index]){index--;}if(index == 0){reverse(nums,0,nums.length-1);}else{int j = nums.length - 1;while(nums[j] <= nums[index - 1]){//不会死循环j--;}swap(nums,j,index - 1);reverse(nums,index,nums.length-1);//右侧降序改升序}}private void reverse(int []nums,int start,int end){while(start < end){swap(nums,start,end);start++;end--;}}private void swap(int []nums,int i,int j){if(nums[i] == nums[j]){return ;}int tmp = nums[j];nums[j] = nums[i];nums[i] = tmp;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！