栈与队列_数据结构

栈
栈：栈是限定再表尾进行插入和删除操作的线性表，栈是线性表

栈的基本知识

目录

• [42.Trapping rain water](#42.Trapping rain water)
• [173.二分查找树迭代器](#173.Binary Search Tree Iterator)

42.Trapping rain water

题目链接

// 这道题要仔细研究
// 解法用很多种，我却一种都不会！！！
// 动态规划的方法，出现运行时间错误
int trap(vector<int>& height)
{
    if(height == null)
        return 0;
    int ans = 0;
    int size = height.size();
    vector<int> left_max(size), right_max(size);
    left_max[0] = height[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = max(height[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
}
// 其实我更喜欢暴力解法
// brute force
class Solution {
public:
    int trap(vector<int>& height) {
        int size=height.size();
        int result=0;
        // 去掉头尾两个元素
        for(int i=1;i<size-1;i++){ 
            int max_left=0;
            int max_right=0;
            for(int j=i;j>=0;j--){
                max_left=max(max_left,height[j]);
            }
            for(int j=i;j<size;j++){
                max_right=max(max_right,height[j]);
            }
            result+=min(max_left,max_right)-height[i];
        }
        return result;    
    }
};

173.Binary Search Tree Iterator

// 自己写成这样
// 有一点不理解。就是 BSTIterator i = BSTIterator(root);
// 不理解这个是如何进行传递的，不理解 参数 i 的含义
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:

    BSTIterator(TreeNode *root) {
        stack<int> iter;
        inorder(root,iter);
        
    }
    void inorder(TreeNode *root,stack<int>&iter){
        if(!root)
            return ;
        stack<TreeNode *>s;
        s.push(root);
        while(root->left){
            s.push(root->left);
            root=root->left;
        }
        while(!s.empty()){
            TreeNode *temp=s.top();
            s.pop();
            iter.push(temp->val);
            if(temp->right){
                s.push(temp->right);
            }
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return iter.size()!=0;
        
    }

    /** @return the next smallest number */
    int next() {
        int temp=iter.top();
        iter.pop();
        return temp
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */
class BSTIterator {
public:
vector<int> v;
int counter;
BSTIterator(TreeNode *root) {       
        counter = 0;
        dfs(root);           
}

void dfs(TreeNode* root){
        if(!root)
                return;

        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
}

/** @return whether we have a next smallest number */
bool hasNext() {
        return counter < v.size();
}

/** @return the next smallest number */
int next() {
        int res = v[counter];
        counter++;
        return res;
}
};