Leetcode_20 天编程能力基础_day18

还有两天哦~

155. Min Stack

Analysis

实现一个最小栈，相比栈而言，其实就多了一个返回栈内最小值的功能，可以直接用一个变量来记录最小值。

Code

底层数据结构就用数组就可以了，用一个变量 tp 作为栈顶指针，再用变量 minimumofstk 记录栈内最小值。

class MinStack {
    int stk[30010];
    int tp, minimumofstk;
public:
    MinStack() {
        tp = -1;
        minimumofstk = INT_MAX;
    }
    
    void push(int val) {
        stk[++tp] = val;
        if(val < minimumofstk) minimumofstk = val;
    }
    
    void pop() {
        int tmp = stk[tp--];
        if(tp == -1) minimumofstk = INT_MAX;
        else if(tmp == minimumofstk) {
            minimumofstk = stk[tp];
            for(int i = 0; i < tp; i++) {
                if(stk[i] < minimumofstk) minimumofstk = stk[i];
            }
        }
    }
    
    int top() {
        return stk[tp];
    }
    
    int getMin() {
        return minimumofstk;
    }
};

这种思路会有一个问题，那就是每次 pop 操作之后都需要更新最小值（尽管 getMin 操作的确是常数时间内完成的），时间复杂度是$O(n)$。
实际上，常数时间内获取最小值的操作可以借助一个辅助栈完成。每次将元素入栈时，都将该元素与辅助栈栈顶元素比较，如果小于，即将该元素放入辅助栈，此时辅助栈栈顶的元素就是主栈内的最小值。

class MinStack {
    stack<int> stk;
    stack<int> min_stk;
public:
    MinStack() {
        min_stk.push(INT_MAX);
    }
    
    void push(int val) {
        stk.push(val);
        min_stk.push(min(min_stk.top(), val));
    }
    
    void pop() {
        stk.pop();
        min_stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return min_stk.top();
    }
};

341. Flatten Nested List Iterator

Analysis

没看懂这题到底什么意思...直接冲向题解区😂。

Code

实际上就是树形结构的扁平化，只不过在整个过程中需要借助一下这个类的内部函数。

class NestedIterator {
    vector<int> vals;
    vector<int>::iterator cur;
    void dfs(const vector<NestedInteger> &nestedList) {
        for(auto &nest: nestedList) {
            if(nest.isInteger()) {
                vals.push_back(nest.getInteger());
            } else {
                dfs(nest.getList());
            }
        }
    }
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        dfs(nestedList);
        cur = vals.begin();
    }
    
    int next() {
        return *cur++;        
    }
    
    bool hasNext() {
        return cur != vals.end();
    }
};

将全部元素全部扁平化的思路，其实有点投机了。因为题目的名称是 list iterator，所以实现的功能应该是迭代到哪一步了，就把那一步展开。

class NestedIterator {
    stack<NestedInteger> st;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for(int i = nestedList.size() - 1; i >= 0; i--) {
            st.push(nestedList[i]);
        }
    }
    
    int next() {
        NestedInteger cur = st.top(); st.pop();
        return cur.getInteger();
    }
    
    bool hasNext() {
        while(!st.empty()) {
            NestedInteger cur = st.top();
            if(cur.isInteger()) {
                return true;
            }
            st.pop();
            for(int i = cur.getList().size() - 1; i >= 0; i--) {
                st.push(cur.getList()[i]);
            }
        }
        return false;
    }
};

其实这个题，写起来很容易，就是着重理解题目的意思。

Summary

与设计模式相关的题，需要读点相关书籍才能理解的更透彻...

---