今天也没学什么新东西，那就给大家上两道力扣算法题叭。
1.合并正序数组并求中位数
这道题在之前的帖子中（指针第四卷）也提到过，但没有详细去讲，今天就详细讲一下这道题。
1.题目剖析
首先看这道题的题目，给定两个正序数组，并求出它们的中位数，再根据下方输入输出提示，我们首先想到的就是合并数组，遍历这两个正序数组，并把其中的元素存放到另一个空数组记作nums3中。这里我们需要注意的一点是在遍历完nums1，并且将nums1中的元素存放进nums3中后，我们开始遍历nums2，但这时存放元素的时候nums3和nums2的下标并不一致，切应该相差nums1Size，相当于是把nums2中的元素接轨到nums1元素的后面。
合并完数组后注意此时nums3中的元素是乱序的，所以我们要对nums3进行排序，这里我用到了C语言标准库函数qsort函数排序，它的底层原理采用快速排序，效率高。
对nums3排完序后就可以去找中位数，注意要分奇数列和偶数列两种情况。
2.代码示例
#include <stdio.h> #include <stdlib.h> int cmp_nums3(const void* p1, const void* p2) { return *((int*)p1) - *((int*)p2); } double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { int nums3[nums1Size + nums2Size]; for(int i=0; i < nums1Size; i++) nums3[i] = nums1[i]; for(int j=0; j < nums2Size; j++) nums3[nums1Size + j] = nums2[j]; qsort(nums3, nums1Size + nums2Size, sizeof(int), cmp_nums3); if((nums1Size + nums2Size) % 2 == 0) return (double)(nums3[(nums1Size + nums2Size) / 2 - 1] + nums3[(nums1Size + nums2Size) / 2]) / 2; else return (double)nums3[(nums1Size + nums2Size) / 2]; }
3.拓展思考
对于这道题来说以上只是常规解法，并没有用到算法（除了qsort函数自带的快速排序用到了分治），那我们还有没有其他更巧妙简洁的方法，比如既然nums1和nums2都是正序数组，是否可以采用插入排序思想，把nums2中的元素插入到nums1中呢？
2.盛最多水的容器
1.题目剖析
首先分析题目的意思简单来说就是求该柱形图的最大面积（要满足木桶原理）
那我们可以采用最暴力的方法把所有面积求出来，然后引入max变量找最大值，并进行动态更新
2.代码示例
int maxArea(int* height, int heightSize) { int max = 0, arr[100]; for (int j = 0; j <= heightSize - 2; j++) { for (int i = j + 1; i <= heightSize - 1; i++) { if (height[j] > height[i]) arr[j] = height[i] * (i - j); else arr[j] = height[j] * (i - j); if (max < arr[j]) max = arr[j]; } } return max; }
3.运行结果
但是力扣身为一个练习算法的平台，一定不会让你这么简单就通过，果不其然，他的最后几组测试用例的长度都是以万为单位的，这样的话你用嵌套for循环至少要循环上百万次，肯定超时。
4.算法改进
我们再来仔细分析一下题目，就用题目给的图去看
假设取左右两边（下标记作0和8）的两条线，那么这个面积记为S，接下来再取0和7，你会发现所构成矩形面积的长在缩小，而宽不变，那么面积一定比S小，那有的人该问了，如果款变量呢，根据木桶原理如果宽变，那也是出现了一个比0的高度还小的宽才导致宽变了，所以我们没必要挨个求每种情况的面积，只需要设置左右两个指针left和right，从两边开始求面积，求完后，如果左边的高度小，就让左指针左移，否则让右指针右移 ，因为两指针移动必然会导致矩形长度变小，那么想让矩形面积变大只能从高度上做文章，然后在定义一个变量max实时更新就行。
5.改进代码示例
int min(int x, int y) { if (x > y) return y; else return x; } int maxArea(int* height, int heightSize) { int left = 0, right = heightSize - 1, max = 0;//计算柱形图面积最大值（双指针） while (left < right) { int area = (right - left) * min(height[left], height[right]); if (area > max) max = area; if (height[right] < height[left]) right--; else left++; } return max; }
