leetcode-0739【完整工程】

题目:

每日温度

关键词：

  单调栈 数组用例比较

思路：

  维护一个递减的下标栈，当前值大于栈顶值时弹出栈顶值，并输出下标距离。

0739.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MY_DEBUG printf
//#define MY_DEBUG
#define MLOGI       MY_DEBUG
#define MLOGE      MY_DEBUG

#define MIN(x, y)       ((x) < (y) ? (x) : (y))
#define MAX(x, y)       ((x) > (y) ? (x) : (y))
#define ARRAY_SIZE(x)   (sizeof(x)/sizeof(x[0]))

typedef struct {
    int *buf;
    int top;
    int size;
} MyStackType;

static MyStackType g_stack = {
        .buf = NULL,
        .top = 0,
        .size = 0
};

int StackPush(int val)
{
    if (g_stack.top >= g_stack.size) {
        return -1;
    }
    MLOGI("---------------------push %d\n", val);
    g_stack.buf[g_stack.top++] = val;
    return 0;
}

int StackPop(void)
{
    if (g_stack.top <= 0) {
        return -1;
    }
    MLOGI("=====================pop %d\n", g_stack.buf[g_stack.top - 1]);
    return g_stack.buf[--g_stack.top];
}

int StackInit(int size)
{
    if (size <= 0) {
        return -1;
    }
    g_stack.buf = (int *)malloc(size * sizeof(int));
    if (g_stack.buf == NULL) {
        return -1;
    }
    g_stack.size = size;
    g_stack.top = 0;
    return 0;
}

void StackDeInit(void)
{
    if (g_stack.buf != NULL) {
        free(g_stack.buf);
        g_stack.buf = NULL;
    }
    g_stack.size = 0;
    g_stack.top = -1;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* dailyTemperatures(int* T, int TSize, int* returnSize)
{
    if ((T == NULL) || (TSize <= 0)) {
        if (returnSize != NULL) {
            *returnSize = 0;
            return NULL;
        }
    }
    if (returnSize == NULL) {
        return NULL;
    }
    int *retBuf = (int *)malloc(sizeof(int) * TSize);
    if (retBuf == NULL) {
        *returnSize = 0;
        return NULL;
    }
    memset(retBuf, 0, sizeof(int) * TSize);
    int ret = StackInit(TSize);
    int i;
    int offset = 0;
    for (i = 0; i <TSize; i++) {
        while((g_stack.top > 0) && (T[i] > T[g_stack.buf[g_stack.top - 1]])) {
            offset = StackPop();
            retBuf[offset] = i - offset;
        }
        StackPush(i);
    }
    *returnSize = TSize;
    StackDeInit();
    return retBuf;
}

测试用例：test_case.cpp

#include <gtest/gtest.h>
#include <gmock/gmock.h>
#include <string.h>

#define MIN(x, y)       ((x) < (y) ? (x) : (y))
#define MAX(x, y)       ((x) > (y) ? (x) : (y))
#define ARRAY_SIZE(x)   (sizeof(x)/sizeof(x[0]))

extern "C" int* dailyTemperatures(int* T, int TSize, int* returnSize);

TEST(FactorialTest, test_case0) {
    int temperatures[] = {73, 74, 75, 71, 69, 72, 76, 73};
    int expectBuf[] = {1, 1, 4, 2, 1, 1, 0, 0};
    int retSize;
    int expectSize = ARRAY_SIZE(temperatures);
    int *retBuf = dailyTemperatures(temperatures, ARRAY_SIZE(temperatures), &retSize);
    printf("retSize=%d\n", retSize);
    int i;
    for (i = 0; i < retSize; i++) {
        printf("%d ", retBuf[i]);
    }
    printf("\n");
    EXPECT_EQ(expectSize, retSize);
    GTEST_ASSERT_EQ(memcmp(expectBuf, retBuf, sizeof(expectBuf)), 0);
}

main.c

#include <gtest/gtest.h>
using namespace std;

int main(int argc, char *argv[])
{
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

构建：CMakeLists.txt

cmake_minimum_required(VERSION 2.8)

SET(TARGET_NAME lc-out)
PROJECT(${TARGET_NAME})

SET(CMAKE_CXX_COMPILER "g++.exe")
SET(CMAKE_C_COMPILER "gcc.exe")

SET(USER_PUBLIC_DIR "D:/leetcode/user_public")

SET(CMAKE_C_FLAGS  "-g")
SET(CMAKE_CXX_FLAGS "${CMAKE_C_FLAGS}")

FILE(GLOB_RECURSE SRC_LIST ${CMAKE_CURRENT_LIST_DIR}/*.cpp ${CMAKE_CURRENT_LIST_DIR}/*.c)
FILE(GLOB_RECURSE REMOVE_CMAKE ${CMAKE_CURRENT_LIST_DIR}/cmake-build-debug/* ${CMAKE_CURRENT_LIST_DIR}/build/*)
LIST(REMOVE_ITEM SRC_LIST ${REMOVE_CMAKE})

# MESSAGE("${CMAKE_CURRENT_LIST_DIR}")
# MESSAGE("SRC_LIST is:" ${SRC_LIST})

include_directories(
        ${USER_PUBLIC_DIR}/include
)

link_directories(
        ${USER_PUBLIC_DIR}/lib
)

ADD_EXECUTABLE(${TARGET_NAME} ${SRC_LIST})
TARGET_LINK_LIBRARIES(${TARGET_NAME}  gtestd gmockd)