2种实现单调栈.md

单调加循环的队列

//循环的队列的实验：1 2 1 ==》 1 2 1 1 2。这就是循环的队列了。
public int[] nextLaege(int[] nums){
	int n = nums.length;
	int[] res = new int[n];
	Arrays.fill(res, -1);
	Deque<Integer> stack = new LinkedList<>();
	for(int i = 0; i < 2*n-1; i++) {
		while(!stack.isEmpty && nums[stack.peek()) < nums[i%n)]) {
			res[stack.pop()] = nums[i%n];
		}
		stack.push(i%n);
	}
	return res;
}

//Dota2参议院的循环队列的使用，
public String predictPartyVictory(String senate) {
//需要利用到的是求余的操作了。还有第二轮的必须是可以分出胜负的。
        int len = senate.length();
        Queue<Integer> radiant =  new LinkedList<>();
        Queue<Integer> dire =  new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (senate.charAt(i) == 'R'){
                radiant.offer(i);
            }else {
                /*add, offer, */
                dire.offer(i);
            }
        }

        while(!radiant.isEmpty() && !dire.isEmpty()) {
            int raIndex = radiant.poll(), diIndex = dire.poll();
            if (raIndex < diIndex){
                radiant.offer(raIndex+len);
            }else {
                dire.offer(diIndex+len);
            }
        }
        return !radiant.isEmpty() ? "Radiant" : "Dire";
    }

官方的题解

	    public int[] maxSubsequence(int[] nums, int k) {
        int length = nums.length;
        int[] stack = new int[k];
        int top = -1;
        int remain = length - k;
        //remain的作用是什么啊？可以删除多少字节的意思。
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (top >= 0 && stack[top] < num && remain > 0) {
                top--;
                remain--;
            }
            if (top < k - 1) {
                stack[++top] = num;
            } else {
                remain--;
            }
        }
        return stack;
    }

认为和那个去除重复字母的题解类似

	public List<Integer> getKLargestNumber(int[] nums, int k){
        int n = nums.length;
        int popCnt = n - k;
        List<Integer> res = new ArrayList<>();
        if(k == 0)
            return res;
        for(int i = 0; i < n; i++) {
            while (!res.isEmpty() && res.get(res.size() - 1) < nums[i] && popCnt > 0) {
                res.remove(res.size() - 1);
                popCnt--;
            }
            if (res.size() < k){
                res.add(nums[i]);
            }else {
                popCnt--;  //注意， 这里容易漏了， 如果没有添加到数组， pop--
            }
        }
        return res;
    }