数据结构与算法实例详解--数组篇

数组是一种基础的数据结构，用于存储一组相同类型的数据元素。它在计算机科学和编程中扮演着重要的角色。数组是一个非常重要且广泛使用的基础数据结构，在算法与数据结构中占有重要地位。了解数组的性质和操作，是学习更复杂数据结构和算法的基础。以下是数组的一些关键概念和特性：

1. 定义

数组是一个固定大小的、连续的内存块，用来存储多个同类型的数据。例如，可以创建一个整型数组来存储一系列整数。

2. 特性

• 大小固定：数组的大小在创建时设定，后续不可更改。
• 元素类型相同：数组中的所有元素必须是同一种类型（例如，整数、浮点数或字符）。
• 随机访问：数组允许通过索引快速访问任意元素，访问时间复杂度为 O(1)。

3. 索引

数组通常从零开始索引，第一个元素的索引为 0，第二个元素的索引为 1，以此类推。

4. 内存布局

在内存中，数组的元素是连续存储的。这意味着可以通过简单的数学运算结合基地址和索引快速计算出任何元素的地址。

5. 常用操作

• 获取元素：通过索引访问数组中的元素，例如 array[i]。
• 修改元素：可以通过索引修改数组某个位置的元素，例如 array[i] = newValue。
• 遍历数组：可以使用循环结构，例如 for 循环，依次访问数组的每个元素。

6. 时间复杂度

• 访问：O(1)
• 插入（在末尾）：O(1)
• 插入（在中间或开头）：O(n)
• 删除（在中间或开头）：O(n)
• 遍历：O(n)

7. 数组的优缺点

优点：

• 高效的随机访问。
• 结构简单，易于实现。

缺点：

• 大小固定，无法动态调整。
• 在中间插入或删除元素时效率较低，需要移动大量元素。

8. 动态数组

由于静态数组的局限性，许多编程语言提供了动态数组（如 Python 的列表、Java 的 ArrayList），允许在运行时动态调整大小。这些数据结构在内部使用数组，但封装了大小调整和元素迁移的逻辑。

9. 应用场景

数组广泛应用于各种场景，如：

• 存储固定数量的元素（如星期天数、月份等）。
• 实现其他数据结构（如栈、队列、哈希表等）。
• 基本算法（如排序、查找算法等）。

OK，话不多说，直接看真题：

LCP 61.气温变化趋势【简单】
题目：
力扣城计划在两地设立「力扣嘉年华」的分会场，气象小组正在分析两地区的气温变化趋势，对于第 i ~ (i+1) 天的气温变化趋势，将根据以下规则判断：

若第 i+1 天的气温 高于 第 i 天，为 上升 趋势
若第 i+1 天的气温 等于 第 i 天，为 平稳 趋势
若第 i+1 天的气温 低于 第 i 天，为 下降 趋势
已知 temperatureA[i] 和 temperatureB[i] 分别表示第 i 天两地区的气温。 组委会希望找到一段天数尽可能多，且两地气温变化趋势相同的时间举办嘉年华活动。请分析并返回两地气温变化趋势相同的最大连续天数。

即最大的 n，使得第 i~i+n 天之间，两地气温变化趋势相同

示例 1：

输入： temperatureA = [21,18,18,18,31] temperatureB = [34,32,16,16,17]

输出：2

解释：如下表所示， 第 2～4 天两地气温变化趋势相同，且持续时间最长，因此返回 4-2=2。

示例 2：

输入： temperatureA = [5,10,16,-6,15,11,3] temperatureB = [16,22,23,23,25,3,-16]

输出：3

提示：

2 <= temperatureA.length == temperatureB.length <= 1000
-20 <= temperatureA[i], temperatureB[i] <= 40
分析问题：
        这道题我们可以借助一个数组来标记这几天的温度变化趋势，根据题意，我们不难得出变化趋势是后一天与今天的温度相比，那么意思就是说最后一天不需要对比，所以只需要遍历从 0到len()-1 即可，那么我们开创的数组的长度也只需要len()-1即可。第一可以避免空间浪费，其次还可以避免把最后一位统计进去。这样我们即可进行以下的代码实现了。

代码实现：

class Solution:
    def temperatureTrend(self, temperatureA: List[int], temperatureB: List[int]) -> int:
        m=len(temperatureA)
        dp1=[0]*(m-1)
        dp2=[0]*(m-1)
        for i in range(m-1):
            if temperatureA[i+1]>temperatureA[i]:
                dp1[i]=1
            elif  temperatureA[i+1]==temperatureA[i]:
                dp1[i]=0
            else: dp1[i]=-1
 
            if temperatureB[i+1]>temperatureB[i]:
                dp2[i]=1
            elif temperatureB[i+1]==temperatureB[i]:
                dp2[i]=0
            else: dp2[i]=-1
        a_max,v=0,0
        for _ in range(m-1):
            if dp1[_]==dp2[_]:
                v+=1
            else:
                a_max=max(a_max,v)
                v=0
        a_max=max(a_max,v)
        return a_max

总结：
        题目总体不难，本来感觉复杂度可以的了，没想到竟然排最后了。还是可以优化优化的。以下是对代码详解以及考点总结。

详解：

首先获取两个温度列表的长度 m 。
初始化两个辅助列表 dp1 和 dp2 ，长度均为 m - 1 。通过遍历两个温度列表，比较相邻元素的大小关系，分别将趋势（上升为 1 ，相等为 0 ，下降为 -1 ）存储在 dp1 和 dp2 中。
然后通过一个循环，比较 dp1 和 dp2 中对应位置的趋势值。如果相同，则连续相同趋势的计数器 v 增加；如果不同，更新最大连续相同趋势长度 a_max ，并将计数器 v 重置为 0 。
循环结束后，再次更新最大连续相同趋势长度 a_max ，并返回其值。
考点：

对列表的遍历和操作。
条件判断和逻辑处理。
动态规划的思想，通过记录中间状态（趋势值）来计算最终结果。
最大值的更新和连续相同值的计数。

“如果你的人生只有柠檬，不妨配盐喝点龙舌兰。 ”——《我是谁：没有绝对安全的系统》