标签： 队列

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

 

限制：

• 1 <= push_back,pop_front,max_value的总操作数 <= 10000
• 1 <= value <= 10^5

双队列空间换时间

1. 一个queue用来保存正常顺序的队列Queue<Integer> queue
2. 另一个双端队列Deque<Integer> deque ,从队尾插入的时候时候需要从队列尾部往前删除比自己小的值，直到遇到一个大于等于当前需要插入的值的时候停止
3. 这样这个双端队列deque从队头读取的时候，能保证，对头元素是当前所有插入的值中的最大值
4. 当从queue中删除头部的元素的时候，对比下deque中队首的元素是否是当前被从queue中删除的那个，如果是的话，则同时删除双端队列deque的队首元素
5. 这样双端队列deque删除队首元素的时候，下一个小于等于当前删除的队首元素的，且位置是位于当前queue队首那个元素到结尾这个区间内的最大元素，那么符合题意的设计就完成了

class MaxQueue {

    Queue<Integer> queue;

    Deque<Integer> deque;

    public MaxQueue() {
        queue = new ArrayDeque<>();
        deque = new ArrayDeque<>();
    }
    
    public int max_value() {
        if (queue.isEmpty()){
            return -1;
        }
        return deque.peekFirst();
    }
    
    public void push_back(int value) {
        queue.add(value);
        while (!deque.isEmpty() && deque.peekLast() < value){
            deque.pollLast();
        }
        deque.offer(value);
    }
    
    public int pop_front() {
        if (queue.isEmpty()){
            return -1;
        }
        if (queue.peek().equals(deque.peekFirst())){
            deque.pollFirst();
        }
        return queue.poll();
    }
}

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

 

限制：

0 <= s 的长度 <= 50000

1. 声明一个HashMap<Character,Integer> firstShowMap记录各个字符第一次出现的位置
2. 声明一个HashSet<Character> moreThenOneSet保存出现超过一次的字符
3. 遍历一遍字符串完成上面两个哈希集合的赋值
4. 遍历firstShowMap，对比moreThenOneSet处理只有出现一次的字符
5. 声明firstSingle保存单个的字符和firstSingleIndex对应的出现位置
6. 遍历firstShowMap的过程中如果找到一个新的只出现过一次的字符，两者比较firstSingleIndex，留下位置跟靠前的那一个

代码

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character,Integer> firstShowMap = new HashMap<>();
        HashSet<Character> moreThenOneSet = new HashSet<>();
        int i = -1;
        while (++i < s.length()){
            if (!firstShowMap.containsKey(s.charAt(i))){
                firstShowMap.put(s.charAt(i),i);
            }else{
                moreThenOneSet.add(s.charAt(i));
            }
        }

        final char[] firstSingle = {' '};
        final int[] firstSingleIndex = {s.length()};
        firstShowMap.forEach((theChar,theIndex)->{
            if (!moreThenOneSet.contains(theChar)){
                if (theIndex < firstSingleIndex[0]){
                    firstSingleIndex[0] = theIndex;
                    firstSingle[0] = theChar;
                }
            }
        });
        return firstSingle[0];
    }
}

思路就是这样，实现形式有很多种
比如

1. firstSingleIndex也可以不存下来，直接回firstShowMap中取到
2. 又或者官方题解中说的那样的moreThenOneSet可以省略，有重复的直接修改firstShowMap对应的value为一个不合理的值，后面判断的时候也就根据这个不合理的值来判断。

21年11月30日，重新做了一次这个题目

class Solution {
    public char firstUniqChar(String s) {
        if (s.length()==0){
            return ' ';
        }
        //重复的
        boolean[] map1 = new boolean[26];
        //第一次出现的位置
        int[] map2 = new int[26];
        Arrays.fill(map2,-1);
        int idx = -1;
        while (++idx < s.length()){
            int charIdx = s.charAt(idx)-'a';
            if (!map1[charIdx]){
                if (map2[charIdx] != -1){
                    map1[charIdx] = true;
                    map2[charIdx] = -1;
                }else{
                    map2[charIdx] = idx;
                }
            }
        }
        char ans = ' ';
        int min = s.length();
        for (int i = 0; i < map2.length; i++) {
            if (map2[i] != -1 &&  map2[i] < min){
                min = map2[i];
                ans = s.charAt(min);
            }
        }
        return ans;
    }
}

再次思考，也可以不用两个map，在一个map上定义更多的状态来实现，除了现有的-1表示默认没处理的情况，也可以再定一个-2为已经有多个相同字符出现的情况

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

 

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对 appendTail、deleteHead 进行 10000 次调用

【此时你需要两个薯片桶】有点意思的设计题

来啊，先去超时买两罐薯片再来解这题呢！~

我们把两个薯片桶当做两个栈，先进后出非常的完美符合。这两个桶分别为A和B

按照如图的这样把两桶桶放好，而薯片就是你要放入的数字了，此时往A桶里放入标记了1,2,3的三个薯片

现在我觉得标记1号的薯片可能味道比较好一点，我想吃那个1号薯片，那么我就把两个桶口相接，把A桶里的薯片都倒入B桶，这样我就可以轻松拿到原先A桶最底部的1号薯片了

此时我还想再往3号薯片后面放一个4号薯片，但是我只想把这个4号薯片放到3号薯片后面，呢么就把B桶里的薯片再都倒入A桶

然后我们继续往A桶里放入第4号薯片

好了，到这里你想吃薯片了没？

class CQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        //把stack2全都倒入stack中，然后再往顶部压入数据
        while (!stack2.isEmpty()){
            int num = stack2.pop();
            stack1.push(num);
        }
        stack1.push(value);
    }
    
    public int deleteHead() {
        if (stack1.isEmpty() && stack2.isEmpty()){
            return -1;
        }
        while (!stack1.isEmpty()){
            int num = stack1.pop();
            stack2.push(num);
        }
        return stack2.pop();
    }
}