数组题目技巧总结（四）

数组题目介绍

数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与各类算法结合的问题B篇。

问题类型与技巧

1. 数组与贪心算法的问题

   贪心算法的宗旨在于每次每次都能到达最大或者最小，即在数组中找到某个公式的最值，让我们能很快解决这个问题。

2. 数组与动态规划的问题

   动态规划最常与数组问题结合，其中最重要的就是找到状态变化的状态转移方程，以及初始条件，一般来说都会创建额外的辅助空间，然后根据初始条件和状态转移方程计算填满辅助数组。

经典题型

• 题目①买卖股票的最好时机

  这道题可以使用动态规划写出状态转移方程，也可以用贪心思想：如果我们在某一天卖出了股票，那么要想收益最高，一定是它前面价格最低的那天买入的股票才可以。因此后续只需要每次找前面的最小值，并且对每天都可以尝试卖一下维护最大收益。

• 题目②合并区间

  这道题的贪心思想主要是对排序后的区间，如果有重叠，直接对区间尾部取最大值。

• 题目③矩阵最小路径和

  这道题主要找到状态转移方程：如果当前的位置是$(i\mathrm{，}j)(i，j)$，上一步要么是$(i-1,j)(i-1,j)$往下，要么就是$(i,j-1)(i,j-1)$往右，取其中较小值与当前位置的值相加就是到当前位置的最小路径和，因此状态转移公式为$dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]dp[i][j]\; =\; min(dp[i-1][j],\; dp[i][j-1])\; +\; matrix[i][j]$

• 题目④子数组最大乘积

  这道题目因为数组可正可负可0，因此有三种状态，最大值则需要比较取其中的较大的一个。用$max[i]max[i]$表示当前下标$ii$及之前的子数组乘积最大值，$min[i]min[i]$表示当前下标$ii$及之前的子数组乘积最小值，那么对于数组下一个元素$arr[i+1]arr[i+1]$，新一轮的最大值要么是$max[i]\ast arr[i+1]max[i]\; *\; arr[i+1]$（$max[i]max[i]$为正，$arr[i+1]arr[i+1]$为正），要么是$min[i]\ast arr[i+1]min[i]\; *\; arr[i+1]$（$min[i]min[i]$为负，$arr[i+1]arr[i+1]$为负），要么就是$arr[i+1]arr[i+1]$（$max[i]max[i]$为负，$arr[i+1]arr[i+1]$为正）。因此循环过程中，每次都是维护最大值与最小值。

• 题目⑤斐波那契数列

  斐波那契数列是非常经典的动态规划的题目，它的转移方程就是其递推公式$fib(n)=fib(n-1)+fib(n-2)fib(n)=fib(n-1)+fib(n-2)$.