LC 面试题 03.01. 三合一

题目描述

这是 LeetCode 上的 面试题 03.01. 三合一 ，难度为 简单。

三合一。

描述如何只用一个数组来实现三个栈。

你应该实现 push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum) 方法。

stackNum 表示栈下标，value 表示压入的值。

构造函数会传入一个 stackSize 参数，代表每个栈的大小。

示例1:

输入：
["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]

输出：
[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。

示例2:

输入：
["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]

输出：
[null, null, null, null, 2, 1, -1, -1]

---

二维数组

题目只要求我们使用「一个数组」来实现栈，并没有限制我们使用数组的维度。

因此一个简单的做法是，建立一个二维数组 data 来做。

二维数组的每一行代表一个栈，同时使用一个 locations 记录每个栈「待插入」的下标。

代码：

class TripleInOne {
    int N = 3;
    // 3 * n 的数组，每一行代表一个栈
    int[][] data; 
    // 记录每个栈「待插入」位置
    int[] locations; 
    public TripleInOne(int stackSize) {
        data = new int[N][stackSize];
        locations = new int[N];
    }
    public void push(int stackNum, int value) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc < stk.length) {
            stk[loc] = value;
            locations[stackNum]++;
        }
    }
    public int pop(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            int val = stk[loc - 1];
            locations[stackNum]--;
            return val;
        } else {
            return -1;
        }
    }
    public int peek(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) return stk[loc - 1];    
        else return -1;
    }
    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == 0;
    }
}

C++ 代码：

class TripleInOne {
public:
    int N = 3;
    vector<vector<int>> data; 
    vector<int> locations; 
    TripleInOne(int stackSize) {
        data.resize(N, vector<int>(stackSize));
        locations.resize(N, 0);
    }
    void push(int stackNum, int value) {
        vector<int>& stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc < stk.size()) {
            stk[loc] = value;
            locations[stackNum]++;
        }
    }
    int pop(int stackNum) {
        vector<int>& stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            int val = stk[--loc];
            locations[stackNum] = loc;
            return val;
        } else {
            return -1;
        }
    }
    int peek(int stackNum) {
        vector<int>& stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) return stk[loc - 1];    
        else return -1;
    }
    bool isEmpty(int stackNum) {
        return locations[stackNum] == 0;
    }
};

• 时间复杂度：所有的操作均为 $O(1)$。
• 空间复杂度：$O(k \times n)$。$k$ 为我们需要实现的栈的个数，$n$ 为栈的容量。

---

一维数组

当然了，我们也能使用一个一维数组来做。

建立一个长度为 $3 \times stackSize$ 的数组，并将 3 个栈的「待插入」存储在 locations 数组。

代码：

class TripleInOne {
    int N = 3;
    int[] data, locations;
    int size;
    public TripleInOne(int stackSize) {
        size = stackSize;
        data = new int[size * N];
        locations = new int[N];
        for (int i = 0; i < N; i++) locations[i] = i * size;
    }
    public void push(int stackNum, int value) {
        int idx = locations[stackNum];
        if (idx < (stackNum + 1) * size) {
            data[idx] = value;
            locations[stackNum]++;
        }
    }
    public int pop(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) {
            locations[stackNum]--;
            return data[idx - 1];
        } else {
            return -1;
        }
    }
    public int peek(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) return data[idx - 1];    
        else return -1;
    }
    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == stackNum * size;
    }
}

C++ 代码：

class TripleInOne {
public:
    int N = 3;
    vector<int> data, locations;
    int size;
    TripleInOne(int stackSize) : size(stackSize), data(stackSize * N), locations(N, 0) {
        for (int i = 0; i < N; i++) locations[i] = i * size;
    }
    void push(int stackNum, int value) {
        int idx = locations[stackNum];
        if (idx < (stackNum + 1) * size) {
            data[idx] = value;
            locations[stackNum]++;
        }
    }
    int pop(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) {
            locations[stackNum]--;
            return data[idx - 1];
        } else {
            return -1;
        }
    }
    int peek(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) return data[idx - 1];
        else return -1;
    }
    bool isEmpty(int stackNum) {
        return locations[stackNum] == stackNum * size;
    }
};

• 时间复杂度：所有的操作均为 $O(1)$。
• 空间复杂度：$O(k \times n)$。$k$ 为我们需要实现的栈的个数，$n$ 为栈的容量。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 面试题 03.01. 三合一 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。