当前位置：首页 > news >正文

O(1) 时间复杂度数据设计题

news 来源：原创 2025/5/9 10:21:48

0x00 preface

所谓 $O (1)$ $A P I$ 设计，并不是说，时间复杂度必须是**“总是”常数级别的。
对于一个操作来说，如果他偶尔是 $O (N)$ 的，大部分时间都是 $O (1)$ 的，并且，这个 $O (1)$ 分摊之后，我们说它的“均摊时间复杂度为 $O (1)$ ”。**

什么是分摊？
对于一个操作，可以分摊的前提是，你这个时间复杂度很高的情况只会执行常数次，那额，分摊到你每一次执行，就是常数+常数还是常数级别，只不过常数比较大罢了。
例如，我们可以看一下官方对维护队列最大值插入操作的分摊解释

删除操作于求最大值操作显然只需要 $O (1)$ 的时间。
而插入操作虽然看起来有循环，做一个插入操作时最多可能会有 $n$ 次出队操作。
但要注意，由于每个数字只会出队一次，因此对于所有的 $n$ 个数字的插入过程，对应的所有出队操作也不会大于 $n$ 次。
因此将出队的时间均摊到每个插入操作上，时间复杂度为 $O (1) 。$

我们知道，计算机世界中，时间与空间复杂度是很难兼得得，因此，在让我们时间 $O (1)$ 时间复杂度时，辅助数据结构(辅助空间)【往往】是必不可少的。
而且，辅助数据结构(辅助空间)往往也是解题的关键！我们在做题的时候，需要积累这些信息。

维护栈最值：从 $e a sy$ 到 $ha r d$
（1）辅助栈保存最值，类似单调栈。需要两个栈。
（2）在“栈”中保存最小值，一个栈，但是栈中有额外数据。
（3）逆天差值法， $O (1)$ 空间复杂度！
维护队列的最值：目前做法唯一，滑动窗口思想，额外 $d e q u e$ 数据结构。

另外，对于有些特殊的题目，数学公式往往能一击必杀 $O (1)$ 。

0x01 数学公式

题目描述

面试题 17.19. 消失的两个数字

思路

由于题目中缺少了两个数字，也就是有两个未知数，我们从数学的角度出发，怎么才能在 $[1, n]$ 中求出两个未知数 $a$ 和 $b$ 呢？
很简单，我们只需要构造 $a$ 和 $b$ 的两个二元方程式即可！
一个方程就是 $a + b = x$ ，这很容易想到，另一个是 $a * a + b * b == y$ ，求他们的平方和。（当前其他公式也是可以的，但是要注意乘法溢出）
平方和公式（ $s=1^2 + 2^2 + ... + k^2$ ）： $\frac{k (k + 1) (k + 2)} {6}$

代码

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {// a * a + b * b = x// a + b = y// get a and b// (a + b) * (a + b) = a * a + b * b + 2 * a * b;// y * y = x + 2 * a * b// 2 * a * b = (y * y - x)// 2 * a * (y - a) = y * y - x//  -> 2ay - 2a*a = y*y - x//  -> 2(aa) - 2y(a) + (y*y-x) = 0;//  -> a = (2y +/- sqry(4y*y - 8(y*y-x))) / 4// b = y - aint n = nums.size() + 2;int a = 0, b = 0;long long x = 0, y = 0;for(int i = 1; i <= n; i ++ )   x += i * i, y += i;// cout << "x: " << x << ' ' << "y: " << y << endl;for(auto &i : nums) x -= i * i, y -= i;// cout << "x: " << x << ' ' << "y: " << y << endl;cout << 2*y << ' ' << y*y-x << endl;a = 2*y - sqrt((4*y*y - 8*(y*y-x)));cout << 4*y*y-8*(y*y-x) << endl;if(a < 0)   a = 2*y + sqrt((4*y*y - 8*(y*y-x)));cout << "a: " << a << endl;a/=4;b = y - a;return {a, b};}
};

参考

数学 && biset
异或

0x02 队列最大值

题目描述

题目描述

思路

维护队列的最大值我们很容易想到滑动窗口，对于滑动窗口来说，我们可以很容易的维护不断添加元素时的最大值，但是当删除元素时，最大值该怎么维护呢？
在滑动窗口中，有一个很重要的性质，那就是如果先入滑动窗口的元素比后入滑动窗口的元素小，那么它就会被滑动窗口删除（这里指的是滑动窗口的头部是最大值的情况）。
先放一放这个结论。
当我们删除原队列的一个元素时，我们肯定希望它也在滑动窗口中也删除（如果存在的话），那么当前元素只有两种可能（存在的话）：

队头
不是队头

如果它是队头，那么很简单，直接删除。不是的话就麻烦了啊，如果它在队列的中间，难道我们要把它之前所有元素取出来，在删除它，再把拿出来的元素再放回去吗？
这肯定是不行，也不需要的！
因为！如果原队列当前删除的元素不是队头的话，说明，后面肯定有比它大的元素入队，并且作为队头，这意味着什么？
好了，结论可以拿出来用了，这意味着，它在滑动窗口已经被删除了！我们不用再删除它了！

代码

class MaxQueue {
private:queue<int> q;   // 保存队列元素deque<int> maxq; // 保存最大值,设计为队头是最大值
public:MaxQueue() {}int max_value() {return maxq.empty() ? -1 : maxq.front();}void push_back(int value) {q.push(value);while(!maxq.empty() && maxq.back() < value)    maxq.pop_back();  // 滑动窗口maxq.push_back(value);}int pop_front() {if(q.empty())   return -1;int value = q.front();  q.pop();if(maxq.front() == value)   maxq.pop_front();  // 是队头则删除，否则不用管return value;}
};

参考

ref

0x03 栈的最小值

题目描述

155

代码1 – 两个栈

class MinStack {
public:stack<int> cur;stack<int> minx;void push(int val) {int min_val = minx.empty() ? val : min(minx.top(), val);cur.push(val);minx.push(min_val);}void pop() {int last = cur.top();cur.pop();minx.pop();}int top() {return cur.top();}int getMin() {return minx.top();}
};

代码2 – 一个“栈”，栈中有额外信息

class MinStack {
private:
// 其实本质上和两个栈没啥区别，但形式上是一个栈！
// 纯纯骗自己 😭typedef struct node_t {int val;int minx;node_t *next;node_t(int _val, int _minx) : val(_val), minx(_minx), next(nullptr) {}} Node;Node *head;public:
// 不带头节点的链表MinStack() : head(nullptr) {}~MinStack() {while(head) {Node *delNode = head;head = head->next;delete delNode;}}void push(int x) {if(head == nullptr) head = new Node(x, x);else {// 因为模拟的是 stack，所以放到头部(head)Node *newNode = new Node(x, min(x, head->minx));   newNode->next = head;head = newNode;}}void pop() {if(head == nullptr) return ;Node *delNode = head;head = head->next;delete delNode;}int top() {if(head == nullptr) return -1;return head->val;}int getMin() {if(head == nullptr) return -1;return head->minx;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(x);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

代码3 – 差值法，无辅助空间，LL 类型 stack

class MinStack {
/* 关于空间复杂度
因为有溢出的可能，所以要使用 longlong 来存储
但是一旦使用 longlong，就意味着空间是 int 的两倍
也就意味着和多开一个辅助栈没啥区别
也就是纯纯的自己骗自己 😭
但是这种差值的思想还是很好的 🤔
*//* 具体的思路就是：
stack用来保存当前插入栈顶的值与之前的最小值的差值，同时维护最小值
因此，最小值是真的最小值，但是top不是真的top，它是top与最小值的差值
1.因为，取最小值就很简单了，直接返回 minx2.当我们插入元素时：
例如，按顺序插入2，3，1，1，4。模拟一下便知道了
我们规定，第一个插入的元素，差值为 0。
push(2)
stack(top): 0
minx      : 2
----------------------
push(3)，先计算3与当前minx的差值：3-minx=3-2=1
1>=0，说明当前元素不小于minx，先插入元素
stack(top): 0 1
minx      : 2 
不用更新最小值
stack(top): 0 1
minx      : 2 
----------------------
push(1)，先计算1与当前minx的差值：1-minx=1-2=-1
-1<0，说明当前元素小于minx，先插入元素
stack(top): 0 1 -1
minx      : 2 2
然后再更新最小值
stack(top): 0 1 -1
minx      : 1
----------------------
push(1)，先计算1与当前minx的差值：1-minx=1-1=0
0>=0，不需要更新最小值，先插入元素
stack(top): 0 1 -1 0
minx      : 1
不需要更新
stack(top): 0 1 -1 0
minx      : 1
----------------------
push(4)，先计算1与当前minx的差值：4-minx=4-1=3
stack(top): 0 1 -1 0 3
minx      : 1
不需要更新最小值
stack(top): 0 1 -1 0 3
minx      : 13.当我们返回top元素时
(1)如果top(diff)的值<0，说明当前元素比之前的元素小
说明，在该元素插入之后，最小心会更新为它的值
因此，此时top=minx而不是top+minx
你可能会问，哎，当前top不是存储的真实的top和minx的差值吗？
我们不应该返回当前top+minx吗？
是这样的没错，但是，还记得上面的push步骤吗
我们的diff是真实的top于它还没插入时的最小值的差值
如果diff>0，说明最小值没变，那么真实的top自然等于现在的top+minx了
但是如果diff<0，就说明，现在的minx被改变了，被谁改变了呢？
当然就是此时插入的真实的top啊
所以说，如果diff<0，说明此时minx就是真实的top4.其实分析了push和top，那么pop就很好分析了
pop无非就是更新minx
如果top也就是diff>=0，说明插入的元素比minx大，minx不更新
如果top也就是diff<0， 说明插入的元素比minx小，minx更新
*/private:stack<long long> st;    // 存储与“当前”最小值的差值long long minx;         // 最小值public:MinStack() : minx(-1) {}void push(int val) {if(st.empty()) {st.push(0);minx = val;}else {long long diff = val - minx;st.push(diff);// diff < 0 --> val < minxminx = diff < 0 ? val : minx;}}void pop() {if(st.empty())  return ;long long diff = st.top();st.pop();// 之前是 minx_new = minx_old + diff;// 现在是 minx_old = minx_new - diff; if(diff < 0)    minx -= diff;}int top() {if(st.empty())  return -1;long long diff = st.top();if(diff < 0)    return minx;return minx + diff;}int getMin() {if(st.empty())  return -1;return minx;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(x);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

代码4 – 差值法，int 类型 stack

class MinStack {
public:typedef long long ll;stack<int> stk;int min_val = -INT_MAX;const ll convert_bias = ((ll)INT_MIN)*(-1);MinStack() {}void push(int val) {if(stk.empty()){stk.push(0);min_val = val;}else{ll diff = (ll)val - min_val;if(diff < 0)min_val = val;if(diff < INT_MIN)diff += convert_bias;else if(diff > INT_MAX)diff -= convert_bias;stk.push((int)diff);}}void pop() {assert(!stk.empty());ll diff = (stk.top());stk.pop();if(min_val + diff < INT_MIN)diff -= convert_bias;else if(min_val - diff < INT_MIN)diff += convert_bias;if(diff < 0)min_val = (min_val - diff);}int top() {assert(!stk.empty());ll diff = stk.top();if(min_val + diff < INT_MIN)diff -= convert_bias;else if(min_val - diff < INT_MIN)diff += convert_bias;if(diff<0) return min_val;else return min_val + diff;}int getMin() {return min_val;}
};

0x00 preface

0x01 数学公式

题目描述

思路

代码

参考

0x02 队列最大值

题目描述

思路

代码

参考

0x03 栈的最小值

题目描述

代码1 – 两个栈

代码2 – 一个“栈”，栈中有额外信息

代码3 – 差值法，无辅助空间，LL 类型 stack

代码4 – 差值法，int 类型 stack

相关文章：