当前位置: 首页 > news >正文

LeetCode42_接雨水

LeetCode42_接雨水

  • 标签:#栈 #数组 #双指针 #动态规划 #单调栈
    • Ⅰ. 题目
    • Ⅱ. 示例
  • 0. 个人方法一:数学角度一
  • 0. 个人方法二:数学角度二
  • 官方题解一:动态规划
  • 官方题解二:单调栈
  • 官方题解三:双指针(推荐)

标签:#栈 #数组 #双指针 #动态规划 #单调栈

Ⅰ. 题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

Ⅱ. 示例

· 示例1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

· 示例 2:
输入:height = [4,2,0,3,2,5]
输出:9

0. 个人方法一:数学角度一

我认为这题和上一题的分糖果是有相像之处的,都是要从左右两侧来判断当前的状态,于是我还是考虑从左和从右分别遍历,看看需要判断达到什么样的条件可以满足题目要求。
(这个方法一有些别出心裁,我找到了除了 height 和雨水外,上方的空间大小,再用长方形面积减去这个大小,再减 height 的和得到了雨水大小)

  1. 新建一个数组保存每个位置的状态
  2. 从左往右遍历:
    将左边第一个非0 height 记为初始标准,持续保持当前标准记录到数组中,遇到更高的height就更新标准,继续持续记录。我们可以发现,到最高点后,后面都会记录为最高点,所以还要从右往左遍历。
    在这里插入图片描述
  3. 从右往左遍历:
    将右边第一个非0 height 记为初始标准,持续保持当前标准,将这个标准和之前记录的标准作差,取绝对值,得到上方空间大小。
    (从右向左正常遍历结果)
    在这里插入图片描述
    (作差取绝对值后的结果)
    (这里的红色就是我要求的上方空间了,这里我在图中还呈现了黑色区域,只是为了方便观看原先height的大小,并不在我记录的数组中)
    在这里插入图片描述
  4. 最后做数学计算,得出结果
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>using namespace std;
class Solution {
public:int trap(vector<int>& height) {int first = 0;  // 左边第一个不为0的数int last = 0;   // 右边第一个不为0的数int highest = 0;   // 最高的数// 找左边第一个不为0的数for (int i=0; i<height.size(); i++){if (height[i] != 0){first = i;break;}}// 找右边第一个不为0的数for (int i=height.size()-1; i>=0; i--){if (height[i] != 0){last = i;break;}}// 找最高的数for (int i=first; i<=last; i++){if (height[i] > highest){highest = height[i];}}int n = last - first + 1;vector<int> except(n, 0);int standard_left = height[first];int standard_right = height[last];// 从左往右遍历for (int i=first; i<=last; i++){if (height[i] > standard_left){standard_left = height[i];}except[i-first] = standard_left;}// 从右往左遍历for (int i=last; i>=first; i--){if (height[i] > standard_right){standard_right = height[i];}except[i-first] = abs(except[i-first] - standard_right);// except[i-first] = min(standard_left, standard_right) - height[i];}int sum_except = accumulate(except.begin(), except.end(), 0);int sum_black = accumulate(height.begin(), height.end(), 0);int water = (last - first + 1) * highest - sum_except - sum_black;// int water = accumulate(except.begin(), except.end(), 0);return water;}
};int main() {Solution solution;vector<int> height = {4,2,0,3,2,5};int result = solution.trap(height);cout << "Trapped water: " << result << endl;  // 应输出 9return 0;std::cin.get();
}

(这个方法麻烦在我需要找左侧和右侧第一个不为0的值,还要找最高的值是多少,来计算长方形面积)
(但是出乎意料的,执行用时却是最短的)

0. 个人方法二:数学角度二

我又想了想,能不能不找那些非0值和最高值,于是有了以下方法:

  1. 首先创建一个数组 water,用于记录每个位置的雨水状态
  2. 从左向右遍历:我们需要一个标准高度 standard_left ,令 standard_left = height[0] 记为初始状态,遍历过程中,只要碰到比这个标准高的 height,就将标准更新为这个更高的 height,并存到数组 water 里。但我们可以发现,到达最高的 height 后,右边就都是取得这个最高值了。这就需要从右往左遍历来去掉多余的“雨水”了。
  3. 从右往左遍历:也是和上一次遍历的逻辑相同,int 一个新的变量 standard_right,但是这次在每个位置:把 min(water[i], standard_right) - height[i] 存到数组 water 里,这次就完全剩下纯“雨水”了,只要对数组进行累积和就行了。
class Solution {
public:int trap(vector<int>& height) {int n = height.size();vector<int> water(n, 0);int standard_left = height[0];int standard_right = height[n-1];for (int i=0; i<n; i++){if (height[i] > standard_left){standard_left = height[i];}water[i] = standard_left;}for (int i=n-1; i>=0; i--){if (height[i] > standard_right){standard_right = height[i];}water[i] = min(water[i], standard_right) - height[i];}int watertotal = accumulate(water.begin(), water.end(), 0);return watertotal;}
};

官方题解一:动态规划

和上述方法二差不多,这里不赘述了

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);}vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);}int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];}return ans;}
};
  • 复杂度分析

    • 时间复杂度:O(n),其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次,计算能接的雨水总量还需要遍历一次。

    • 空间复杂度:O(n),其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。

官方题解二:单调栈

在这里插入图片描述

class Solution {
public:int trap(vector<int>& height) {int ans = 0;stack<int> stk;int n = height.size();for (int i = 0; i < n; ++i) {while (!stk.empty() && height[i] > height[stk.top()]) {int top = stk.top();stk.pop();if (stk.empty()) {break;}int left = stk.top();int currWidth = i - left - 1;int currHeight = min(height[left], height[i]) - height[top];ans += currWidth * currHeight;}stk.push(i);}return ans;}
};
  • 复杂度分析

    • 时间复杂度:O(n),其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。

    • 空间复杂度:O(n),其中 n 是数组 height 的长度。空间复杂度主要取决于栈空间,栈的大小不会超过 n。

官方题解三:双指针(推荐)

在这里插入图片描述

class Solution {
public:int trap(vector<int>& height) {int ans = 0;int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}
};
  • 复杂度分析

    • 时间复杂度:O(n),其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。

    • 空间复杂度:O(1)。只需要使用常数的额外空间。

http://www.xdnf.cn/news/181369.html

相关文章:

  • 杭电oj(1010、1015、1241)题解
  • 【数据可视化-39】2009-2019年亚马逊50大畅销书数据集可视化分析
  • 迷你世界UGC3.0脚本Wiki世界模块管理接口 World
  • Mysql中隐式内连接和显式内连接的区别
  • (26)VTK C++开发示例 ---将点坐标写入PLY文件
  • linux:进程的替换
  • 大模型时代具身智能:从理论突破到产业落地的全链路解析
  • 自动伴随无人机说明文档
  • Netmiko 源码关键流程图
  • pytorch学习使用
  • 深入解析MyBatis-Plus中的lambdaUpdate与lambdaQuery
  • OpenCV 图形API(65)图像结构分析和形状描述符------拟合二维点集的直线函数 fitLine2D()
  • 文章记单词 | 第47篇(六级)
  • java map中的key区分大小写吗
  • ChatGPT与DeepSeek在科研论文撰写中的整体科研流程与案例解析
  • 【git】添加项目到已有gitee仓库
  • vue组件间通信
  • 蓝桥杯 9.生命之树
  • 【Multipath】dm软链接相关问题定位
  • 前端高频面试题day3
  • Python装饰器:函数增强的秘密武器
  • 使用ZXing开发安卓扫码功能
  • 【C++】C++11新特性(一)
  • 【前端】element表格X轴滚动优化拖拽滚动
  • 函数式编程之 Optional
  • 海底世界-第16届蓝桥第4次STEMA测评Scratch真题第5题
  • 【jax】ms(毫秒)和 μs(微秒)
  • Leetcode395.至少有 K 个重复字符的最长子串
  • Qt从零开始(1)了解
  • Golang | 倒排索引Value的设计