数组题目介绍

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

问题类型与技巧

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

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

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

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

经典题型

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

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

  • 题目②合并区间

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

  • 题目③矩阵最小路径和

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

alt

  • 题目④子数组最大乘积

    这道题目因为数组可正可负可0,因此有三种状态,最大值则需要比较取其中的较大的一个。用max[i]max[i]表示当前下标ii及之前的子数组乘积最大值,min[i]min[i]表示当前下标ii及之前的子数组乘积最小值,那么对于数组下一个元素arr[i+1]arr[i+1],新一轮的最大值要么是max[i]arr[i+1]max[i] * arr[i+1]max[i]max[i]为正,arr[i+1]arr[i+1]为正),要么是min[i]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]为正)。因此循环过程中,每次都是维护最大值与最小值。 alt

  • 题目⑤斐波那契数列

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