栈

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

栈的基本知识

目录

42.Trapping rain water

// 这道题要仔细研究// 解法用很多种，我却一种都不会！！！// 动态规划的方法，出现运行时间错误int trap(vector
    
     & height){    if(height == null)        return 0;    int ans = 0;    int size = height.size();    vector
     
       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 forceclass Solution {public:    int trap(vector
      
       & height) {        int size=height.size();        int result=0;        // 去掉头尾两个元素        for(int i=1;i
       
        =0;j--){                max_left=max(max_left,height[j]);            }            for(int j=i;j
       
      
     
    

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
    
      iter;        inorder(root,iter);            }    void inorder(TreeNode *root,stack
     
      &iter){        if(!root)            return ;        stack
      
       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
       
         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;}};