1. 剑指 Offer II 039. 直方图最大矩形面积
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
暴力法
遍历整个heights列表，每次都以当前的height作为高，计算面积，此时只需向左和向右找到第一比当前低的柱子，即为左右边界，然后更新最大面积
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
# 遍历每一个高度
for h in range(len(heights)):
i, j = h-1, h+1
# 找出左边界
while i>=0 and heights[i]>=heights[h]:
i -= 1
# 找右边界
while j<len(heights) and heights[j]>=heights[h]:
j += 1
# 计算宽度
width = j-i-1
# 更新最大面积
maxArea = max(maxArea, heights[h]*width)
return maxArea
时间复杂度 O ( n 2 ) O(n^2) O(n2)
使用单调栈
算法-直方图中的最大矩形
基本思想：维护一个单调递增的堆栈
- 新建一个空栈queue，将 A[0] 压入栈中，此时 A[0] 位于栈顶
- 对于即将入栈的A[i]，如果A[i] 比queue[-1]大，那么将其入栈。如果两者相等，跳过，继续下一个元素。如果比queue[-1]小，以heights[queue[-1]]为高的矩形width是无法增加了，因此计算以该高度的矩形面积，并更新最大面积
算法流程如下： 以[3、2、5、6、1、4、4]为例
-
堆栈[ ]，开始扫描i从0到6；
-
i=0，因为堆栈为空，把i=0入栈 此时堆栈为[0]
-
i=1，因为a[i] =2 < a[top] = a[0] =3，所以这个时候0出栈，并且计算a[0]作为矩形最小高度的面积，因为堆栈已空，所以左边界L就是0，右边界R就是i−1=0；所以最大面积就是a[0]×(R−L+1)=3；此时堆栈为[ ]，然后再把i=1入栈。此时堆栈[1]，如上图。
-
i=2，因为a[i] =5 > a[top] = a[1] =2，所以i=2入栈。此时堆栈[1,2]
-
i=3，因为a[i] =6 > a[top] = a[2] =5，所以i=3入栈。此时堆栈[1,2,3]
-
i=4，因为a[i] =1 < a[top] = a[3] =6，所以3要出栈，并且计算a[3]=6作为矩形最小高度的面积，左边界就是栈顶下一个值加1，L=2+1=3，右边R=i−1=3，所以最大面积就是a[3]×(R−L+1)=6 ; 此时堆栈[1,2]。如上图。
注意: 此时a[i] =1 < a[top] = a[2] =5，所以2也要出栈，并且计算a[2]=5作为矩形最小高度的面积，左边就是栈顶下一个值加1，L=1+1=2，右边R=i−1=3，所以最大面积就是a[2]×(R−L+1)=10 ;此时堆栈[1]。如上图
再此时a[i] =1 < a[top] = a[1] =2，所以1也要出栈，并且计算a[1]=2作为矩形最小高度的面积，因为栈已空，则左边界为0，右边界R=i−1=3，所以最大面积就是a[1]×(R−L+1)=8 ，小于10，取10 ; 最后i=4入栈。此时堆栈[4]。如上图。 -
i=5，因为a[i] =4 > a[top] = a[4] =1，所以i=5入栈。【此时堆栈[4,5]】
-
i=6，因为a[i] =4 = a[top] = a[4] =1，跳过。【此时堆栈[4,5]】
-
i=7，扫描完毕了，此时a[4]，a[5]，a[6]必然单调增。然后再一个个出栈。
-
top=5出栈，计算面积，L=4+1=5,右边没值，相当于右边还有一个a[i=7]=0的矩形，那么R=7−1=6，所以面积就是a[5]×(R−L+1)=8。【此时堆栈[4]】。如上图。
-
top=4出栈，计算面积，栈空，左边为0，右边没值，相当于右边还有一个a[i=7]=0的矩形，那么R=7−1=6，所以面积就是a[4]×(R−L+1)=7。【此时堆栈[ ]】。如上图。
程序如下：我们在heights最后加上0，这样获取到最后的递增堆栈不需要再回头重新遍历，因为最后为0，会出发while，对stack进行pop
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 初始直接将第一个index放入队列
queue = [0]
maxArea = 0
heights.append(0)
for i in range(1, len(heights)):
while queue and heights[i]<=heights[queue[-1]]:
idx = queue.pop()
# 左边界
left = queue[-1]+1 if queue else 0
# 右边界
right = i-1
width = right-left+1
maxArea = max(maxArea, width*heights[idx])
queue.append(i)
#while queue:
# idx = queue.pop()
# right = len(heights)-1
# left = idx
# width = right-left+1
# maxArea = max(maxArea, width*heights[idx])
#return maxArea
2. 剑指 Offer II 040. 矩阵中最大的矩形
给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。注意：此题 matrix 输入格式为一维 01 字符串数组。
输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。
基本思路：
- 从上到下遍历矩阵，以矩阵的每一行作为基线，看成一个直方图，一个n行的矩阵就有n个直方图，分别对这n个直方图求最大面积即可；
- 用一个heights数组来记录以某一行作为基线的直方图的每根柱子的高度，如果矩阵中某个格子的值为0，那么它所在的柱子的高度为0；如果矩阵中某个格子的值为1，那么它所在的柱子的高度是以上一行作为基线的直方图同一位置的柱子的高度加1；
class Solution:
def maximalRectangle(self, matrix: List[str]) -> int:
matrix = [list(map(int, list(item))) for item in matrix]
maxS = 0
for i in range(len(matrix)):
if i == 0:
maxS = max(maxS, self.getRectangleArea(matrix[i]))
else:
# 更改每行中直方图的高
for k in range(len(matrix[i])):
if matrix[i-1][k] != 0 and matrix[i][k]==1:
matrix[i][k] += matrix[i-1][k]
maxS = max(maxS, self.getRectangleArea(matrix[i]))
return maxS
# 计算直方图中最大矩形面积
def getRectangleArea(self, heights):
queue = [0]
heights.append(0)
maxArea = 0
for i in range(1, len(heights)):
while queue and heights[queue[-1]]>heights[i]:
idx = queue.pop()
left = queue[-1]+1 if queue else 0
right = i-1
width = right-left+1
maxArea = max(maxArea, width*heights[idx])
queue.append(i)
return maxArea
3. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
解题思路：
将二维网格看成一个无向图，竖直或水平相邻的 11 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。
最终岛屿的数量就是我们进行深度优先搜索的次数
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
# 从头开始遍历
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
if i >= len(grid) or i<0 or j>=len(grid[0]) or j<0 or grid[i][j]=="0":
return
# 遍历到1置为0，进行下一个便利
if grid[i][j] == "1":
grid[i][j] = "0"
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)