下一个更大的数(二)

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型一维数组
*/
func nextBigger( nums []int ) []int {
    n:=len(nums)
    ans:=make([]int,n)
    for i,_:=range ans{
        ans[i]=-1
    }
    stk:=[]int{}
    for i,x:=range append(nums,nums...){
        for len(stk)>0&&nums[stk[len(stk)-1]]<x{
            ans[stk[len(stk)-1]]=x
            stk=stk[:len(stk)-1]
        }
        stk=append(stk,i%n)
    }
    return ans
}

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/3923970e95b140fdb65e6c00bcda403d?tpId=196&tqId=40444&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        环形数组问题：
            先将数组展开，新数组看作是nums + nums[:-1]，新数组的长度变为0 ~ 2*n-2；当然我们也可以对n取模，这样就不需要分配空间了
        建立单调递减栈，栈中存储元素下标
        遍历新数组0 ~ 2n-2：
            若stack为空 或者 nums[i] < stack[-1]：
                下标i%n入栈
            否则：
                栈顶元素出栈
                res[stack[-1]] = nums[i]
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n), 单调栈的长度
    """

    def nextBigger(self, nums):
        # write code here
        n = len(nums)

        res, stack = [-1] * n, []
        for i in range(2 * n - 1):
            while stack and nums[stack[-1]] < nums[i % n]:
                idx = stack.pop()
                if res[idx] == -1:
                    res[idx] = nums[i % n]
            stack.append(i % n)
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums = [2, 3, 4, 1]

    nums = [4, 3, 2, 1]

    res = sol.nextBigger(nums)

    print res

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> nextBigger(ArrayList<Integer> nums) {
        // write code here
        int size = nums.size();
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            // 全部置为-1
            result.add(i, -1);
        }
        Stack<Integer> stack = new Stack<>();
        // 数组double

        for (int i = 0; i < size; i++) {
            nums.add(nums.get(i));
        }
        for (int i = 0; i < nums.size(); i++) {
            while (!stack.isEmpty() && nums.get(i) > nums.get(stack.peek())) {
                Integer pop = stack.pop();
                if (pop < size) {
                    result.set(pop, nums.get(i));
                }
            }
            stack.push(i);
        }

        return result;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> nextBigger (ArrayList<Integer> nums) {
        // write code here
        Stack<Integer> s = new Stack<>();
        int n = nums.size();
        int[] temp = new int[n];
        for(int i=n*2-1;i>=0;i--){
            while(!s.empty()&&s.peek()<=nums.get(i%n)){
                s.pop();
            }
            temp[i%n]=s.empty()?-1:s.peek();
            s.push(nums.get(i%n));
        }
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=0;i<n;i++){
            res.add(temp[i]);
        }
        return res;
    }
}