首页 > 其他分享 >代码随想录day49 || 42、接雨水 84、柱状图中最大的矩形

代码随想录day49 || 42、接雨水 84、柱状图中最大的矩形

时间:2024-09-03 12:14:05浏览次数:10  
标签:right int 随想录 42 height 柱状图 res stack left

42、接雨水

image

func trap(height []int) int {
	// 双指针思路,按照列计算雨水高度,分别计算每一列左右高于当前高度的最高柱子高度,然后通过min(left, right) - height[i] 得出当前列的雨水体积
	var res int
	var left, right int
	for i:=1; i<len(height)-1; i++ {
		left, right = height[i], height[i]
		for j:=i+1; j<len(height); j++ {
			if height[j] > right {
				right = height[j]
			}
		}
		for j:=i-1; j>=0; j-- {
			if height[j] > left {
				left = height[j]
			}
		}


		res += (min(left, right) - height[i]) * 1
	}

	return res
}
// 时间复杂度是n^2, 空间是1

// 上面解法对于左右最高高度计算涉及到重复,所以考虑空间换时间,用两个数组分别记录当前位置的左右最高高度
func trap(height []int) int {
	// 双指针思路,按照列计算雨水高度,分别计算每一列左右高于当前高度的最高柱子高度,然后通过min(left, right) - height[i] 得出当前列的雨水体积
	var res int
	var left = make([]int, len(height))
	var right = make([]int, len(height))

	left[0] = height[0]
	for i:=1; i<len(height)-1; i++ {
		left[i] = max(height[i], left[i-1])
	}
	right[len(height) - 1] = height[len(height) - 1]
	for i:=len(height)-2; i>=0; i--{
		right[i] = max(height[i], right[i+1])
	}

	//fmt.Println(left, right)
	for i:=1; i<len(height)-1; i++ {
		res += (min(left[i], right[i]) - height[i]) * 1
	}

	return res
}

image

// 单调栈解法, 坑太多,注意单调栈保存的是索引!!!!!,别直接比较了,要取heithg[idx]
func trap(height []int) int {
	// 单调栈,
	var res int
	var stack []int
	for i:=0; i<len(height); i++{
		for len(stack) > 0 && height[i] >= height[stack[len(stack) - 1]] {
			top := stack[len(stack) - 1]
			stack = stack[ : len(stack) - 1]
			if len(stack) > 0 {
				left := stack[len(stack) - 1]
				right := i
				res += (min(height[left], height[right]) - height[top]) * (right - left - 1)
			}
		}
		stack = append(stack, i)
	}
	return res
}

84、柱状图中最大的矩形

image

func largestRectangleArea(heights []int) int {
	// 单调栈 找到左右第一个小于当前元素的位置,然后计算面积
	// 递减栈
	// 大于栈顶 入栈  小于等于 计算面积
	if len(heights) == 1{
		return heights[0]
	}
	var m int
	// 细节首尾+0 // 分别处理[2,3,4]  [4,3,2] 这两种单调的样例
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	var stack []int
	stack = append(stack, 0)
	for i:=0; i<len(heights); i++ {
		for len(stack) > 0 && heights[i] <= heights[stack[len(stack) - 1]] {
			top := stack[len(stack) - 1]
			stack = stack[: len(stack) - 1]
			if len(stack) > 0 {
				var left, right, res int
				left = stack[len(stack) - 1]
				right = i
				res = heights[top] * (right - left - 1)
				m = max(m, res)
			}
		}

		stack = append(stack, i)
	}
	return m
}

标签:right,int,随想录,42,height,柱状图,res,stack,left
From: https://www.cnblogs.com/zhougongjin55/p/18394300

相关文章

  • 【最新原创毕设】基于微信小程序的老年人健康医疗信息服务平台设计+24246(免费领源码)可
    摘 要老年人健康是社会关注的重点之一,随着我国人口老龄化程度的增加,老年人的健康问题逐渐凸显。为了更好地满足老年人的健康需求,提高医疗服务质量和效率,开发一个基于SpringBoot的老年人健康医疗信息服务平台是十分必要的。老年人健康医疗信息服务平台利用Java语言,通过spring......
  • 「代码随想录算法训练营」第五十二天 | 图论 part10
    目录Floyd算法题目:97.小明逛公园A*算法题目:126.骑士的攻击最短路算法总结Floyd算法Floyd算法用于求解多源最短路问题(求多个起点到多个终点的多条最短路径)。在前面学习的dijkstra算法、Bellman算法都是求解单源最短路的问题(即只能有一个起点)。注意:Floyd算法对边的权值正负没......
  • 代码随想录算法训练营|Day01 LeetCode 704.二分查找,27.移除元素,977.有序数组的平方
    数组理论基础数组是存放在连续空间上的相同类型数据的集合数组的元素是不能删的,只能覆盖704.二分查找LeetCode:704.有序数组的平方classSolution{public:intsearch(vector<int>&nums,inttarget){intlength=nums.size();inti=0......
  • 代码随想录算法训练营,9月2日 | 242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1
    哈希表理论基础1.根据关键码的值而直接进行访问的数据结构(直白来讲其实数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素);2.哈希表都是用来快速判断一个元素是否出现集合里;3.哈希函数:把值对应到哈希表的函数;哈希碰撞:映射到哈希表同一个索引......
  • HJ42 学英语
    给你一个数字,输出它的英文单词预处理特殊数字和基本数字然后就特判有没有1e6以上,有没有1e3以上,……有就去掉后面的6位数或者3位数,然后用扔子函数里当3位数处理了我连forty和ninety都写错。。。。。。。。==1#include<bits/stdc++.h>2usingnamespacestd;3stringw......
  • 【代码随想录Day6】哈希表Part01|判断一个元素是否出现集合里
    哈希表理论基础文章讲解:哈希表理论基础要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。242.有效的字母异位词题目链接/文章讲解/视频讲解:有效的字母异位词定义一个哈希表record,遍历s,记录s中每个字母出现的次数,遍历t,减去t中每个字母出现的次数,遍历......
  • 42. typedef
    9.4typedeftypedef为C语言的关键字,作用是为一种数据类型(基本类型或自定义数据类型)定义一个新名字,不能创建新类型与#define不同,typedef仅限于数据类型,而不是能是表达式或具体的值#define发生在预处理,typedef发生在编译阶段#include<stdio.h>typedefintINT;typedefcharBY......
  • 代码随想录day48 || 739, 每日温度 496, 下一个更大元素 I 503, 下一个更大元素II
    739每日温度funcdailyTemperatures(temperatures[]int)[]int{ //双指针 varres=make([]int,len(temperatures)) fori:=0;i<len(temperatures);i++{ forj:=i+1;j<len(temperatures);j++{ iftemperatures[j]>temperatures[i]{ res[i]=j......
  • 042.CI4框架CodeIgniter,控制器过滤器Filter配合Services的使用
    01、Config中的Services.php代码如下:<?phpnamespaceConfig;useApp\Libraries\Tx_Auth;useCodeIgniter\Config\BaseService;classServicesextendsBaseService{//用户权限类publicstaticfunctionuser_auth($getShared=true){echo......
  • 代码随想录算法day4 - 哈希表2
    题目1454.四数相加II给你四个整数数组nums1、nums2、nums3和nums4,数组长度都是n,请你计算有多少个元组(i,j,k,l)能满足:0<=i,j,k,l<nnums1[i]+nums2[j]+nums3[k]+nums4[l]==0示例1:输入:nums1=[1,2],nums2=[-2,-1],nums3=[-1,2],nums4......