[数据结构与算法]4.LeetCode刷题day04

LeetCode刷题day04

1.题目1：在栈基础上加上返回栈中最小值操作

【思路】加上一个辅助栈，用来存放最小值，数据栈每压入一个数据，辅助栈也压入一个数据，辅助栈压入这个数和栈顶数的最小值。

【代码】

class MyStack {
public:
    void push(int val) {
        st.push(val);
        if (stMin.empty()) {
            stMin.push(val);
        } else {
            stMin.push(min(stMin.top(), val));
        }
    }
    void pop() {
        st.pop();
        stMin.pop();
    }
    int getMin() {
        if (stMin.empty()) {
            return -1;
        } else {
            return stMin.top();
        }
    }
private:
    stack<int> st; //数据栈
    stack<int> stMin; //辅助栈
};

2.题目2：用栈结构实现队列

【思路】利用两个栈，一个输入栈，一个输出栈。进队列 操作将数据放入输入栈，出队列操作，看看输出栈有没有数据，有的话弹出栈顶元素，否则将输入栈全部放入输出栈，再弹出输出栈栈顶。

【代码】

class MyQueue {
public: 
    MyQueue() {
        
    }
    void push(int val) {
        stIn.push(val);
    }
    void pop() {
        int res = peek();
        if (res != -1) {
            stOut.pop();
        }
    }
        int peek() {
        if (stOut.empty()) { //输出栈为空
            if (stIn.empty()) { //输入栈也为空不能弹出
                return -1;
            } else { //输出栈为空，输入栈不为空
                while (!stIn.empty()) {
                    stOut.push(stIn.top());
                    stIn.pop();
                }
           		return stOut.top();
            }
        } else { //输出栈有数据
            return stOut.top();
        }
    }
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
private:
    stack<int> stIn; //输入栈
    stack<int> stOut; //输出栈
};

3.题目3：利用队列实现栈

【思路】准备两个队列，一个队列用来备份，把que1最后面元素以外的元素都被分到que2，然后弹出最后面的元素，再把其他元素从que2导回que1.

【代码】

class MyStack {
private:
    queue<int> que1, que2;
public:
    MyStack() {

    }
    
    void push(int x) {
        que1.push(x);
    }
    
    int pop() {
        int size = que1.size();
        size--;
        while (size--) {
            que2.push(que1.front());
            que1.pop();
        }
        int tmp = que1.front();
        que1.pop();
        while (!que2.empty()) {
            que1.push(que2.front());
            que2.pop();
        }
        return tmp;
    }
    
    int top() {
        if (empty()) {
            return -1;
        } else {
            return que1.back();
        }
    }
    
    bool empty() {
        return que1.empty();
    }
};

4.题目4：接雨水

【思路1】单调栈。

class Solution {
public:
    int trap(vector<int>& nums) {
        int res = 0; //存放每个元素左右离它最近的元素的下标
        stack<list<int>> st;
        //遍历阶段
        for (int i = 0; i < nums.size(); ++i) {
            if (st.empty() || nums[i] < nums[st.top().back()]) {
                st.push(list<int>{i});
            } else if (nums[i] == nums[st.top().back()]) {
                st.top().push_back(i);
            } else {
                while (!st.empty() && nums[i] > nums[st.top().back()]) {
                    list<int> tmp = st.top();
                    st.pop();
                    int left = st.empty() ? -1 : st.top().back();
                    int right = i;
                    if (left == -1) {
                        continue;
                    }
                    int w = right - left - 1;
                    int h = min(nums[left], nums[right]) - nums[tmp.back()];
                    res += w * h;
                }
                if (st.empty() || nums[st.top().back()] != nums[i]) {
                    st.push(list<int>{i});
                } else {
                    st.top().push_back(i);
                }
            }
        }
        return res;
    }
};

【思路2】双指针。能够接到雨水的量分成**每个格子能装下雨水的量相加。每个格子能装下的雨水的量是每个格子左右两边最大高度的最小值减去当前高度的值。**那么我们只要遍历一遍数组，用左右两边较小的最大高度的值减去当前高度即可，那么问题就变成了如何求左右两边最大高度。

方法一：可以用两个辅助数组，分别装下从左往右和从右往左遍历的最大高度，然后每次遍历的时候，从辅助数组里取值就行。

方法二：可以用双指针方法，第一个位置和最后一个位置不可能接的了水，我们先令leftMax = arr[0], rightMax = arr[arr.size() - 1]。left = 0， right = arr.size() - 1。

此时，left的左侧最大值和right的右侧最大值已经确定，而left的右侧最大值和right的左侧最大值没有遍历完数组还不能确定，但是如果当前leftMax > rightMax， 那么right位置接的雨水的量就已经能确定了，因为能接的是左右两边最大值最小的那一个，右侧最大值已经确定，虽然左侧最大值还未确定，但是比右侧最大值大，那么直接用右侧最大值减去当前值就行。求出right位置能接雨水的最大值后，right -= 1，左侧同理。即哪侧最大值比较小就结算哪一侧。

【代码1】辅助数组

int trap(vector<int>& height) {
    int n = height.size();
    //创建辅助数组,left从左往右看最大值，right从右往左看最大值
    vector<int> left(n) , right(n);
    int leftMax = 0, rightMax = 0;
    for (int i = 0; i < n; ++i) {
        leftMax = max(leftMax, height[i]);
        rightMax = max(rightMax, height[n - i - 1]);
        left[i] = leftMax;
        right[i] = rightMax; 
    }
    //计算结果
    int res = 0;
    for (int i = 1; i < n - 1; ++i) {
        int h = min(left[i - 1], right[n - i - 2]);
        if (h > height[i]) {
            res += h - height[i];
        }
    }
    return res;
}

【代码2】使用双指针

int trap(vector<int>& height) {
    int n = height.size();
    int leftMax = height[0], rightMax = height[n - 1];
    int res = 0;
    int left = 0, right = n - 1;
    while (left < right) {
        if (leftMax < rightMax) { //如果左边最小值小结算左边
            res += max(min(leftMax, rightMax) - height[++left], 0);
            leftMax = max(height[left], leftMax);
        } else { //右边最小值小结算右边
            res += max(min(leftMax, rightMax) - height[--right], 0);
            rightMax = max(height[right], rightMax);
        }
    }
    return res;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖