数据结构核心实战：栈、队列、哈希表与数组

前 K 个高频单词

自定义比较器，优先按频率降序，频率相同则按字典序升序。使用哈希表统计词频，配合优先队列筛选 Top K。

class Solution {
    using psi = pair<string, int>;
    struct cmp {
        bool operator()(const psi& p1, const psi& p2) {
            if (p1.second == p2.second) return p1.first < p2.first;
            return p1.second > p2.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ret(k);
        unordered_map<string, int> hash;
        for (auto& str : words) hash[str]++;
        priority_queue<psi, vector<psi>, cmp> pq;
        for (auto& e : hash) {
            pq.push(e);
            if (pq.size() > k) pq.pop();
        }
        while (!pq.empty()) {
            ret[--k] = pq.top().first;
            pq.pop();
        }
        return ret;
    }
};

数据流的中位数

使用两个堆平衡数据：大根堆存较小的一半，小根堆存较大的一半。保持两堆大小差不超过 1，中位数即为堆顶或堆顶平均值。

class MedianFinder {
    priority_queue<int> left; // 大根堆
    priority_queue<int, vector<int>, greater<int>> right; // 小根堆
public:
    void addNum(int num) {
        if (left.size() == right.size()) {
            if (left.size() && num <= left.top()) left.push(num);
            else { right.push(num); left.push(right.top()); right.pop(); }
        } else {
            if (num >= left.top()) right.push(num);
            else { left.push(num); right.push(left.top()); left.pop(); }
        }
    }
    double findMedian() {
        if (left.size() == right.size()) return (left.top() + right.top()) / 2.0;
        return left.top();
    }
};

栈与队列

点击消除

利用 string 模拟栈操作，遇到相同字符则回退。注意题目要求空串返回 "0" 而非整数 0。

#include <iostream>
using namespace std;

int main() {
    string str, st;
    cin >> str;
    for (char ch : str) {
        if (!st.empty() && st.back() == ch) {
            st.pop_back();
            continue;
        }
        st.push_back(ch);
    }
    cout << (st.empty() ? "0" : st);
    return 0;
}

最小栈

设计辅助栈记录历史最小值。主栈正常操作，辅助栈仅在压入更小或相等元素时同步更新，出栈时若与辅助栈顶一致则同步弹出。

class MinStack {
public:
    MinStack() {}
    void push(int val) {
        _st.push(val);
        if (_minst.empty() || val <= _minst.top()) {
            _minst.push(val);
        }
    }
    void pop() {
        if (_st.top() == _minst.top()) _minst.pop();
        _st.pop();
    }
    int top() { return _st.top(); }
    int getMin() { return _minst.top(); }
private:
    stack<int> _st;
    stack<int> _minst;
};

栈的压入、弹出序列

模拟入栈过程，每压入一个元素就检查是否与弹出序列当前目标匹配，匹配则立即弹出并移动弹出指针。最终栈空则合法。

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int i = 0;
        for (int e : pushV) {
            _st.push(e);
            while (!_st.empty() && _st.top() == popV[i]) {
                _st.pop();
                ++i;
            }
        }
        return _st.empty();
    }
private:
    stack<int> _st;
};

用队列实现栈

入栈时将新元素放入非空队列，随后将原有元素依次移入该队列尾部，使新元素位于队头，从而模拟后进先出特性。

class MyStack {
    queue<int> q;
public:
    MyStack() {}
    void push(int x) {
        int n = q.size();
        q.push(x);
        while (n--) {
            q.push(q.front());
            q.pop();
        }
    }
    int pop() {
        int res = q.front();
        q.pop();
        return res;
    }
    int top() { return q.front(); }
    bool empty() { return q.empty(); }
};

用栈实现队列

双栈结构：一个负责入栈，一个负责出栈。出栈时若空栈为空，则将入栈所有元素翻转压入出栈栈，再弹出。

class MyQueue {
    stack<int> st1, st2;
    void out() {
        while (st1.size()) {
            st2.push(st1.top());
            st1.pop();
        }
    }
public:
    MyQueue() {}
    void push(int x) { st1.push(x); }
    int pop() {
        if (st2.empty()) out();
        int res = st2.top();
        st2.pop();
        return res;
    }
    int peek() {
        if (st2.empty()) out();
        return st2.top();
    }
    bool empty() { return st1.empty() && st2.empty(); }
};

LCR 125. 图书整理 II

同用栈实现队列，通过两个栈完成队列的先进先出逻辑。

class CQueue {
    stack<int> st1, st2;
public:
    CQueue() {}
    void appendTail(int value) { st1.push(value); }
    int deleteHead() {
        if (st2.empty()) {
            while (st1.size()) {
                st2.push(st1.top());
                st1.pop();
            }
        }
        int res = -1;
        if (st2.size()) {
            res = st2.top();
            st2.pop();
        }
        return res;
    }
};

设计循环队列

使用数组配合取模运算实现循环。多开一个空间以区分队空（head==tail）和队满（(tail+1)%size==head）状态。

typedef struct {
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->head == (obj->tail + 1) % (obj->k + 1);
}

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->a = (int*)malloc(sizeof(int) * (k + 1));
    pq->head = pq->tail = 0;
    pq->k = k;
    return pq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;
    obj->a[obj->tail++] = value;
    obj->tail %= obj->k + 1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;
    obj->head++;
    obj->head %= obj->k + 1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[(obj->tail - 1 + obj->k + 1) % (obj->k + 1)];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

数组

删除有序数组中的重复项

快慢指针法。快指针遍历数组，慢指针指向下一个不重复元素的位置。遇到不同元素则覆盖并推进慢指针。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 1;
        for (int fast = 1; fast < nums.size(); ++fast) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

数组中出现次数超过一半的数字

方法一：候选法（摩尔投票） 时间复杂度 O(N)，空间 O(1)。维护候选值和计数器，票数归零则更换候选，抵消不同元素后剩余即为众数。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        int val = 0;
        int count = 0;
        for (int e : numbers) {
            if (count == 0) {
                val = e;
                ++count;
            } else {
                count = (val == e) ? ++count : --count;
            }
        }
        return val;
    }
};

方法二：排序法 众数数量过半，排序后中间位置必为众数。时间复杂度 O(N log N)。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
    }
};

哈希表

两数之和

暴力枚举效率低。利用哈希表存储已遍历元素的索引，查找 target - current 是否存在，实现 O(N) 时间复杂度。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.count(target - nums[i]))
                return {i, hash[target - nums[i]]};
            hash[nums[i]] = i;
        }
        return {};
    }
};

面试题 01.02. 判定是否互为字符重排

方法一：排序比较 长度不同直接返回假，排序后字符串相等即互为重排。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        return s1 == s2;
    }
};

方法二：哈希计数 统计字符频次，遍历第二个字符串时递减计数，若出现负数则不是重排。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int hash[26] = {};
        for (auto e : s1) hash[e - 'a']++;
        for (auto e : s2) {
            if (hash[e - 'a']) hash[e - 'a']--;
            else return false;
        }
        return true;
    }
};

存在重复元素

利用 unordered_set 去重特性，或排序后检查相邻元素，亦可使用哈希表记录已见元素。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (auto e : nums) {
            if (hash.count(e)) return true;
            hash.insert(e);
        }
        return false;
    }
};

存在重复元素 II

在哈希表中记录元素上次出现的索引，若再次出现且索引差小于等于 K，则返回真。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.count(nums[i]) && abs(i - hash[nums[i]]) <= k)
                return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};

字母异位词分组

对每个字符串排序作为 Key，原字符串作为 Value 存入哈希表。Key 相同的字符串即为异位词。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (auto& s : strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string>> ret;
        for (auto& [a, b] : hash) ret.push_back(b);
        return ret;
    }
};