【题目链接】
ybt 1116：最长平台
OpenJudge NOI 1.9 12:最长平台
洛谷 B2097 最长平台
【题目考点】
1. 数组中做统计
2. 求最大值
【解题思路】
解法1：遍历并计数
- 设临时统计长度len（初值为0），最大长度maxLen（初值0），上一个数字lastNum（初值设为与要输入的数字都不同的数字，如-1）
- 将数据输入整型数组a
- 遍历数组a
- 如果当前查看的元素a[i]与上一个数字lastNum相同，那么len增加1
- 如果当前查看的元素a[i]与上一个数字lastNum不同，那么完成对一个“平台”的长度统计，看这个平台的长度是不是比当前已知的最大长度maxLen更大，如果是，那么将maxLen设为该长度。而后要看的是一个新的数字a[i]的平台，将lastNum设为a[i]，已经统计了1个数字a[i]，将len设为1。
- 遍历结束后，还要尝试更新一次maxLen，因为最后统计的平台长度还没与maxLen比较。
- 输出maxLen
解法2：双指针（尺取法）
设左指针l，右指针r，指向平台的两端。左右指针之间的元素（包括两端）都是相同的。
- 如果a[l]等于a[r]，那么右指针向后移。
- 如果a[l]不等于a[r]，那么这个平台的长度（相同元素的个数）为
r-l，更新平台的最大值。然后让l = r，l从当前r位置开始，再取下一个平台
解法3：动态规划
- 状态定义：dp[i]为以下标i为结尾的平台长度
- 初始状态：
dp[1] = 1 - 状态转移方程：
如果a[i-1]与a[i]不同，那么以下标i为结尾的平台长度为1
如果a[i-1]与a[i]相同，那么以下标i为结尾的平台长度为dp[i-1]+1
即：dp[i] = a[i-1] == a[i] ? d[i-1]+1 : 1
求dp数组的最大值，即为最长平台
【题解代码】
解法1：遍历并计数
#include <bits/stdc++.h> using namespace std; int main() {
int n, len = 0, maxLen = 0, lastNum = -1, num;//len:平台长度 maxLen:最大平台长度 lastNum:上一个数。 cin >> n; for(int i = 0; i < n; ++i) {
cin >> num; if(num == lastNum)//如果这个数和上一个数相同 len++; else//如果这个数和上一个数不同 {
if(len > maxLen)//求平台最大值 maxLen = len; lastNum = num; len = 1; } } if(len > maxLen) maxLen = len; cout << maxLen; return 0; } 讯享网
解法2：双指针
讯享网#include <bits/stdc++.h> using namespace std; int main() {
int n, a[105], mx = 0;//mx:最大长度 cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int l = 1, r = 1; r <= n; r++)//l：左指针 r：右指针 {
if(a[r] != a[l]) {
mx = max(mx, r - l); l = r; } } cout << mx; return 0; }
解法3：动态规划
#include <bits/stdc++.h> using namespace std; int main() {
int n, a[105], dp[105], mx = 0; cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; dp[1] = 1; for(int i = 2; i <= n; ++i) {
dp[i] = a[i] == a[i-1] ? dp[i-1]+1 : 1; mx = max(mx, dp[i]); } cout << mx; return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/123269.html