408算法题leetcode--第27天

42. 接雨水

题目地址：42. 接雨水 - 力扣（LeetCode）

题解思路：暴力，接雨水的总和 = 每一列接水的总和；一列的接水数量 = min(左边最高，右边最高) - 当前列的高度

时间复杂度：O(n^2)

空间复杂度：O(1)

代码:

class Solution {
public:
    int trap(vector<int>& height) {
        // 暴力
        int ret = 0;
        int size = height.size();
        for(int i = 0; i < size; i++){
            if(i == 0 || i == size - 1){
                continue;
            }
            int left = i, right = i;
            for(int j = i - 1; j >= 0; j--){
                if(height[j] > height[left]){
                    left = j;
                }
            }
            for(int j = i + 1; j < size; j++){
                if(height[j] > height[right]){
                    right = j;
                }
            }
            if(left != i && right != i){
                ret += min(height[left], height[right]) - height[i];
            }
        }
        return ret;
    }
};

优化思路：对于内层for循环寻找左右最大的高度，可以进行预处理操作，用单调栈提前保存；如注释

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    int trap(vector<int>& height) {
        // 递增栈：三个数据，当前遍历的高度，top指向底部的下标，top的下一个指向左边最高的数
        // S = 高（min(h[i], h[top.next]) - h[top]） * 宽（i - top.next - 1）
        if(height.size() <= 2) return 0;
        stack<int>stk;
        stk.push(0);
        int ret = 0;
        int size = height.size();
        for(int i = 1; i < size; i++){
            if(height[i] <= height[stk.top()]){
                stk.push(i);
            } else {
                while(!stk.empty() && height[i] > height[stk.top()]){
                    int mid = stk.top();
                    stk.pop();
                    if(!stk.empty()){
                        int h = min(height[i], height[stk.top()]) - height[mid];
                        int w = i - stk.top() - 1;
                        ret += h * w;
                    }
                }
                stk.push(i);
            }
        }
        return ret;
    }
};

108. 将有序数组转换为二叉搜索树

题目地址：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

题解思路：dfs

时间复杂度：O(n)

空间复杂度：O(logn)

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(vector<int>& nums, int left ,int right){
        // 参数和返回类型
        // 终止条件
        // 递归逻辑
        if(left > right){
            return nullptr;
        }
        // 分割
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums, 0, nums.size() - 1);
    }
};