490.迷宫#
题目描述#
由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。 给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。
提示
可以买卖多次
示例 1#
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出：true
解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。示例 2#
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出：false
解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。限制#
- m == maze.length
- n == maze[i].length
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1.
- start.length == 2
- destination.length == 2
- 0 <= startrow, destinationrow <= m
- 0 <= startcol, destinationcol <= n
- 球和目的地都在空地上，且初始时它们不在同一位置
- 迷宫 至少包括 2 块空地
题解#
思路 1：暴力循环#
算法流程：
2 次循环分别找出最大价格和最小价格
复杂度分析：
- 时间复杂度
O(N^2)) - 空间复杂度
O(1)
代码#
```go
func maxProfit_1(prices []int) int {
ans := 0
for i := 0; i < len(prices); i++ {
for j := i + 1; j < len(prices); j++ {
ans = max(ans, prices[j]-prices[i])
}
}
return ans
}
```
总结#
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：awesome-golang-algorithm